【剑指offer】面试题17：打印从1到最大的n位数

绝地灬酷狼 2022-06-12 08:30 140阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

**解法1**  
例如输入数字3  
可以当成排列如下数字：  
000  
001  
002  
…  
997  
998  
999  
即打印出数字的全排列。  
所以可以递归求解

**解法2**  
递增，每次在最低位+1，然后处理出现数字10的情况  
这里有一个点要注意，怎么判断打印结束，有两种做法：  
1.用字符串比较算法，和”999…99”即最大的数比较，这样时间复杂度为O(n)，不可取  
2.判断最高位是否发生了进位，时间复杂度为O(1)，我使用这种方法

## 代码（解法1） ##

public static void Print1ToMaxOfNDigits_1(int n) {
        if(n <= 0)
            return;
        char[] digits = new char[n];
        Print1ToMaxOfNDigits_1(digits, n-1);
    }
    
    /**
     * 递归，实现全排列
     */
    private static void Print1ToMaxOfNDigits_1(char[] digits, int index) {
        if(index == -1) {
            PrintDigit(digits);
            return;
        }
        for(int i = 0; i < 10; ++i) {
            digits[index] = (char) ('0' + i);
            Print1ToMaxOfNDigits_1(digits, index-1);
        }
    }
    
    /**
     * 打印digits，注意开头不要打印0
     */
    private static void PrintDigit(char[] digits) {
        boolean zeroFlag = true;
        for(int i = digits.length-1; i >= 0; --i) {
            if(digits[i] == '0' && zeroFlag)
                continue;
            System.out.print(digits[i]);
            zeroFlag = false;
        }
        if(zeroFlag == false) {
            System.out.print(' ');
        }
    }

## 解法2 ##

public static void Print1ToMaxOfNDigits_2(int n) {
        if(n <= 0)
            return;
        char[] digits = new char[n];
        for(int i = 0; i < digits.length; ++i) {
            digits[i] = '0';
        }
        while(Increment(digits)) {
            PrintDigit(digits);
        }
    }
    
    /**
     * 递增 
     */
    private static boolean Increment(char[] digits) {
        digits[0] += 1;
        for(int i = 0; i < digits.length; ++i) {
            int num = digits[i] - '0';
            if(num == 10) {
                if(i == digits.length-1) {
                    return false;
                }
                digits[i+1] += 1;
                digits[i] = '0';
            }
            else {
                break;
            }
        }
        return true;
    }
    
    /**
     * 打印digits，注意开头不要打印0
     */
    private static void PrintDigit(char[] digits) {
        boolean zeroFlag = true;
        for(int i = digits.length-1; i >= 0; --i) {
            if(digits[i] == '0' && zeroFlag)
                continue;
            System.out.print(digits[i]);
            zeroFlag = false;
        }
        System.out.print(' ');
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    private static void test1() {
        _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(1);
        System.out.println();
        _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(2);
        System.out.println();
        _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(3);
        System.out.println();
        System.out.println();
    }
    
    private static void test2() {
        _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(0);
        System.out.println();
        _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(-1);
        System.out.println();
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews