java剑指 offer 17. 打印从1到最大的n位数_依嘫_吃代码的博客-爱代码爱编程
题目所属分类
暴力+分治的思想
原题链接
输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。
代码案例:输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
题解
暴力解法
class Solution {
public int[] printNumbers(int n) {
int end = (int)Math.pow(10, n) - 1;
int[] res = new int[end];
for(int i = 0; i < end; i++)
res[i] = i + 1;
return res;
}
}
分治的思想
class Solution {
StringBuilder res;
int count = 0, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public String printNumbers(int n) {
this.n = n;
res = new StringBuilder(); // 数字字符串集
num = new char[n]; // 定义长度为 n 的字符列表
dfs(0); // 开启全排列递归
res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
return res.toString(); // 转化为字符串并返回
}
void dfs(int x) {
if(x == n) { // 终止条件:已固定完所有位
res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部,使用逗号隔开
return;
}
for(char i : loop) { // 遍历 ‘0‘ - ’9‘
num[x] = i; // 固定第 x 位为 i
dfs(x + 1); // 开启固定第 x + 1 位
}
}
}