天天看点

面试题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);
    }
}