剑指 Offer 17. 打印从1到最大的n位数

题目

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

思路

本题应该考虑的是大数问题，但是返回数组为int[]。。。所以两种方法都做一下

方法一：普通解法（不考虑大数问题）

枚举从 1 到 10^n - 1，返回int数组

class Solution{
          
   
	public int[] printNumbers(int n){
          
   
		int[] res = new int[(int) Math.pow(10,n) - 1];
		for(int i = 0; i < res.length; i++){
          
   
			res[i] = i + 1;
		}
		return res;
	}
}

方法二：全排列解法

在数字很大的情况下，哪怕long类型也无法承载，那必须要用字符串保存。 对于本题其实就是对数字1位数到n位数0 ~ 9的全排列，其中要注意的是数字开头不应该有0。

为了能够测试通过，最后把字符串形式变成了int形式，其实应该返回字符串数组 （力扣的问题）

算法流程：

1. 为了避免数字开头出现0，先把首位first固定，first取值范围为1~9
2. 用digit表示要生成的数字的位数，本题要从1位数一直生成到n位数，对每种数字的位数都生成一下首位，所以有个双重for循环
3. 生成首位之后进入递归生成剩下的digit - 1位数，从0~9中取值
4. 递归的中止条件为已经生成了digit位的数字，即index == digit，将此时的数num转为int加到结果res中

java代码如下：

class Solution {
          
   
	int[] res;
	int count = 0;
	
	public int[] printNumbers(int n){
          
   
		// 考虑大数的全排列 回溯生成
		res = new int[(int)Math.pow(10,n) - 1];
		for(int digit = 1; digit <= n; digit++){
          
   // 数据位数遍历
			for(char first = 1; first <= 9; first++){
          
   // 首位选择 1-9
				char[] num = new char[digit];
				num[0] = first;
				dfs(1, num, digit);
			}
		}
		return res;
	}
	
	private void dfs(int index, char[] num, int digit){
          
   
		if(index == digit){
          
   
			res[count++] = Integer.parseInt(String.valueOf(num));
			return;
		}
		for(char i =0; i <= 9; i++){
          
   
			num[index] = i;
			dfs(index + 1, num , digit);
		}
	}
}