【剑指Offer】打印1到最大的n位数

Posted on | In ,

题目

输入数字n，按顺序打印出从1到最大的n为十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。

跳进面试官的陷阱

1
2
3
4
5
6
public void Print1ToMaxOfNDigits(int n) {
    int number = (int) Math.pow(10, n);

    for (int i = 1; i < number; i++)
        System.out.println(i);
}

在字符串上模拟数字加法的解法，绕过陷阱才能拿到Offer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public void Print1ToMaxOfNDigits(int n) {
    char[] number = new char[n];
    Arrays.fill(number, '0');

    while (!Increment(number)){
        PrintNumber(number);
        System.out.println();
    }
}

private boolean Increment(char[] number){
    int carry = 0;

    for (int i = number.length - 1; i >= 0; i--){
        int sum = number[i] - '0' + carry;

        if (i == number.length - 1)
            sum++;

        carry = sum / 10;

        if (carry == 1){
            if (i == 0)
                return true;

            number[i] = (char) (sum % 10 + '0');
        }
        else
            number[i] = (char) (sum + '0');
    }

    return false;
}

private void PrintNumber(char[] number){
    boolean isBeginning0 = true;

    for (int i = 0; i < number.length; i++){
        if (isBeginning0 == true && number[i] != '0')
            isBeginning0 = false;

        if (isBeginning0 == false)
            System.out.print(number[i]);
    }
}

把问题转换成数字排列的解法，递归让代码更简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public void Print1ToMaxOfNDigits(int n) {
    char[] number = new char[n];
    Arrays.fill(number, '0');

    for (int i = 0; i <= 9; i++){
        number[0] = (char) (i + '0');
        Print1ToMaxOfNDigits(number, 0);
    }
}

private void Print1ToMaxOfNDigits(char[] number, int index){
    if (index == number.length - 1){
        PrintNumber(number);
        return;
    }

    for (int i = 0; i <= 9; i++) {
        number[index+1] = (char) (i + '0');
        Print1ToMaxOfNDigits(number, index + 1);
    }
}

private void PrintNumber(char[] number){
    boolean isBeginning0 = true;

    for (int i = 0; i < number.length; i++){
        if (isBeginning0 == true && number[i] != '0')
            isBeginning0 = false;

        if (isBeginning0 == false)
            System.out.print(number[i]);
    }

    if (isBeginning0 == false)
        System.out.println();
}

相关题目

定义一个函数，在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围，我们也要把它当做大数问题来处理。