Print numbers from 1 to the largest number with N digits by recursion.
Notice
It's pretty easy to do recursion like:
recursion(i) {
if i > largest number:
return
results.add(i)
recursion(i + 1)
}
however this cost a lot of recursion memory as the recursion depth maybe very large. Can you do it in another way to recursive with at most N depth?
Have you met this question in a real interview?
Yes
Example
Given N = 1
, return [1,2,3,4,5,6,7,8,9]
.
Given N = 2
, return [1,2,3,4,5,6,7,8,9,10,11,12,...,99]
.
分析:
我们可以按“层”打印,什么意思呢?
第一层 1 - 9 = 1 to (pow(10, 1) - pow(10, 0))
第二层: 10 - 99 = 10 to (pow(10, 2) - pow(10, 1))
第三层: 100 - 999 = 100 to (pow(10, 3) - pow(10, 2))
...
看到规律了吧。
public class Solution {
/**
* @param n: An integer.
* return : An array storing 1 to the largest number with n digits.
*/
public List<Integer> numbersByRecursion(int n) {
List<Integer> list = new ArrayList<Integer>();
if (n <= ) return list;
// start[0] refers to the start number for the current levevl.
// start[1] refers to the exponent.
int[] start = {, };
helper(n, list, start);
return list;
} public void helper(int n, List<Integer> list, int[] start) {
if (n == ) return;
for (int i = ; i <= (int)(Math.pow(, start[]) - Math.pow(, start[] - )); i++) {
list.add(start[]++);
}
start[]++;
helper(n - , list, start);
}
}