浙江网站建设品牌设计,linux wordpress 区别,国外做的好的医疗网站,泗县建设局网站【问题描述】[中等]
输入数字 n#xff0c;按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3#xff0c;则打印出 1、2、3 一直到最大的 3 位数 999。示例 1:输入: n 1
输出: [1,2,3,4,5,6,7,8,9]说明#xff1a;用返回一个整数列表来代替打印
n 为正整数【解答思路】…【问题描述】[中等]
输入数字 n按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3则打印出 1、2、3 一直到最大的 3 位数 999。示例 1:输入: n 1
输出: [1,2,3,4,5,6,7,8,9]说明用返回一个整数列表来代替打印
n 为正整数
【解答思路】
1. 直接打印 时间复杂度O(10^N) 空间复杂度O(1) 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;}
2. 大数打印 时间复杂度O(N) 空间复杂度O(1)
class Solution {int[] res;int nine 0, count 0, start, n;char[] num, loop {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};public int[] printNumbers(int n) {this.n n;res new int[(int)Math.pow(10, n) - 1];num new char[n];start n - 1;dfs(0);return res;}void dfs(int x) {if(x n) {String s String.valueOf(num).substring(start);// 解决是0的串 0 00 000 0000 if(!s.equals(0)) res[count] Integer.parseInt(s);if(n - start nine) start--;return;}for(char i : loop) {if(i 9) nine;num[x] i;dfs(x 1);}nine--;}
}
【总结】
1.大数全排列模板
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 位为 idfs(x 1); // 开启固定第 x 1 位}}
}
2.全排序一般使用递归处理/回溯法
3.注意回溯时条件要还原
转载链接https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
