打印从1到最大的n位数，考虑大数（Python and C++解法）
2021-05-01 10:27
标签：最大的 ret 定时 temp str 最大的n位数 c_str 输出 put 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: n = 1 来源：力扣（LeetCode） 该题被LeetCode简化了，本文考虑大数情况下的解法： 常见基本数据类型的取值范围都是有限的，因此，大数的表示应用字符串 String 类型。使用 int 类型时，每轮可通过 +1 生成下个数字，而此方法无法应用至 String 类型，且String 类型的数字的进位操作效率较低。 由于所生成的数字的特点，生成的列表实际上是 n 位数的全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。递归生成全排列基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n = 2时，固定十位为 0 - 9，按顺序依次递归，固定个位 0 - 9 后，终止递归并添加数字字符串。 解法中使用的int是为了通过leetcode,实际使用时可以不用转换。 作者：jyd 打印从1到最大的n位数，考虑大数（Python and C++解法） 标签：最大的 ret 定时 temp str 最大的n位数 c_str 输出 put 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13217926.html题目：
输出: [1,2,3,4,5,6,7,8,9]
链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof思路：
链接：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/
来源：力扣（LeetCode） Python解法：
1 class Solution:
2 def printNumbers(self, n: int) -> List[int]:
3 res = [] # 存放结果
4 num = [‘0‘] * n # 起始数字定义为n个‘0‘字符组成的列表
5
6 def dfs(index): # index指被固定的那一位
7 if index == n: # 递归终止条件，已经固定完所有位
8 res.append(int(‘‘.join(num))) # 转换为int只是让结果通过
9 return # 递归调用是栈使用的过程，返回时是返回到上一层继续执行
10 for i in range(10): # 遍历当前位上的每一个元素
11 num[index] = str(i)
12 dfs(index + 1) # 固定下一位
13 dfs(0) # 从最高位开始递归
14 return res[1:]
C++解法：
1 class Solution {
2 public:
3 vectorint> res;
4 vectorint> printNumbers(int n) {
5 vectorint> output;
6 string num(n, ‘0‘); // string初始化为n个‘0’的方法
7 dfs(0, n, num);
8 vectorint>::iterator it = res.begin(); // 指向容器首位的迭代器
9 res.erase(it); // 删除迭代器所指的元素
10 return res;
11 }
12 void dfs(int index, int nn, string s) { // index指被固定的那一位
13 if (index == nn) { // 递归终止条件
14 res.push_back(atoi(s.c_str())); // string先转换为字符数组，再转换为数字
15 return;
16 }
17 for (int i = 0; i 10; i++) {
18 char temp = i + ‘0‘; // 数字转换为字符
19 s[index] = temp; // 字符再添加进入string
20 dfs(index + 1, nn, s);
21 }
22 }
23 };
上一篇：聚类算法和分类算法总结
文章标题：打印从1到最大的n位数，考虑大数（Python and C++解法）
文章链接：http://soscw.com/essay/80816.html