面試題12. 列印1到最大的n位數

題目描述：

輸入數字n，按順序列印從1到最大的n位十進制數，比如輸入3，列印出1、2、3 … 999。

思路1，用加法：

如果n很小，那麼完全可以用（長）整型來實作。

public static void print(int n) {
  int num = 1;
  while(n-- > 0) {
    num *= 10;
  }
  for(int i = 1; i < num; i++) {
    System.out.println(i);
  }
}      

如果n很大很大，必須用字元串來模拟數字。

• 首先，初始化一個長度為n的字元串，并把字元串上的每一位全部初始化為’0’
• 然後模拟字元串加法，每次都加1，并列印出來。

思路2，用字元的全排列：

對于n位數字，每一位數字都從 0 ~ 9 之間取值，n位數字就是n個全排列。

我們把這些全排列寫出來，然後列印出來就行了。

注意，不要列印出前幾位的0。

全排列的核心代碼如下：

static char[] arr = {'0','1','2','3','4','5','6','7','8','9'};

public static void solution2(int n) {
  char[] num = new char[n];
  for(int i = 0; i < 10; i++) {
    num[0] = arr[i];
    core(num, 0); // 開始遞歸
  }
}

public static void core(char[] num, int index) {
       if(index == num.length-1) {
        print(num);
           return ;
       }
       for(int i = 0; i < 10; i++) {
        num[index + 1] = arr[i];
        core(num, index + 1);
       }
}      

/**
 * description：列印1到n的數字
 *     方法1. 用int
 *     方法2. 字元串模拟加法
 *     方法3. 全排列
 * @author lijialin
 *
 */

public class Main {
    
    // 方法1，當n很小時，使用int表示數字
    
    public static void solution1(int n) {
        int num = 1;
        while(n-- > 0) {
            num *= 10;
        }
        for(int i = 1; i < num; i++) {
            System.out.println(i);
        }
    }
    
    
    // 方法3， 當n放大時，int表示不下，用全排列
    
    static char[] arr = {'0','1','2','3','4','5','6','7','8','9'};
    
    public static void solution2(int n) {
        char[] num = new char[n];
        for(int i = 0; i < 10; i++) {
            num[0] = arr[i];
            core(num, 0); // 開始遞歸
        }
    }
    
    public static void core(char[] num, int index) {
        if(index == num.length-1) {
            print(num);
            return ;
        }
        for(int i = 0; i < 10; i++) {
            num[index + 1] = arr[i];
            core(num, index + 1);
        }
    }
    
    public static void print(char[] num) {
        boolean isBeginning = true;
        for(int i = 0; i < num.length; i++) {
            if(isBeginning && num[i] != '0') {
                isBeginning = false;
            }
            if(!isBeginning) {
                System.out.print(num[i]);
            }
        }
        System.out.println();
    }
    
    // main
    public static void main(String[] args) {
        // test case 1
        int n = 3;
        solution1(n);
        solution2(n);
    }
}