力扣对应题目链接：LCR 135. 报数 - 力扣（LeetCode）
牛客对应题目链接：打印从1到最大的n位数_牛客题霸_牛客网 (nowcoder.com)
一、《剑指Offer》内容
二、分析题目
1、暴力解法
2、用字符串模拟数字加法
3、递归全排列解法
假设 n=3，要输出的数其实就是三位数的全排列（000，001，002，...，999。注意：000 不能输出），用递归来表示出这个过程即可。
三、代码
1、暴力解法
//写法一
class Solution {
private:vector<int> res;
public:vector<int> countNumbers(int cnt) {int n=1;while(cnt--)n*=10;for(int i=1; i<n; i++)res.push_back(i);return res;}
};//写法二
class Solution {
private:vector<int> res;
public:vector<int> countNumbers(int cnt) {for(int i=1; i<pow(10, cnt); i++)res.push_back(i);return res;}
};//写法三
class Solution {
private:vector<int> res;
public:vector<int> countNumbers(int cnt) {string maxValue;while(cnt--)maxValue+='9';for(int i=1; i<=stoi(maxValue); i++)res.push_back(i);return res;}
};2、用字符串模拟数字加法
class Solution {
private:vector<int> res;
public:bool increment(string& s){bool isOverflow = false;int carry = 0;for (int i = s.size() - 1; i >= 0; i--){int cur = s[i] - '0' + carry;if (i == s.size() - 1)cur++;if (cur >= 10){if (i == 0)isOverflow = true;else{carry = 1;s[i] = cur - 10 + '0';}}else{s[i] = cur + '0';break;}}return isOverflow;}void printNumbers(string& s){bool isBeginningZero = true;string tmp;for (int i = 0; i < s.size(); i++){if (isBeginningZero && s[i] != '0')isBeginningZero = false;if (!isBeginningZero)tmp += s[i];}res.push_back(stoi(tmp));}vector<int> countNumbers(int cnt) {if (cnt <= 0) return res;string s(cnt, '0');while (!increment(s))printNumbers(s);return res;}
};3、递归全排列解法
class Solution {
private:vector<int> res;
public:void printNumbers(string& s){bool isBeginningZero = true;string tmp;for (int i=0; i<s.size(); i++){if(isBeginningZero && s[i]!='0')isBeginningZero=false;if(!isBeginningZero)tmp+=s[i];}if(tmp!="") res.push_back(stoi(tmp));}void permutation(string& s, int length, int index){if(index==length-1){printNumbers(s);return;}for(int i=0; i<10; i++){s[index+1]=i+'0';permutation(s, length, index+1);}}vector<int> countNumbers(int cnt) {if(cnt<=0) return res;string s(cnt, '0');for(int i=0; i<10; i++){s[0]=i+'0';permutation(s, cnt, 0);}return res;}
};四、扩展
在前面的代码中，我们都是用一个 char 型字符表示十进制数字的一位。8 个 bit 的 char 型字符最多能表示 256 个字符，而十进制数字只有 0~9 的 10 个数字。因此用 char 型字符串来表示十进制的数字并没有充分利用内存，造成了一些浪费。
有没有更高效的方式来表示大数？
通过使用 string 进行求解（上面的方法都可以转换成 string 来求解，下面写一个 dfs）。
- 第一层遍历 n，1 位数、2 位数、3 位数...
- 因为第一位数不能取 0，所以第一位数单独拉出来遍历，故第二层遍历 1~9，代表第一位数只能取 1~9
- 然后 dfs，遍历 2~n 的每一位数字，取值范围 0~9
注意：无需回溯，因为保存结果的是 string，不用引用传递就行。
dfs 的过程：
//大数解法（dfs） class Solution { private:vector<int> res; public:void dfs(int k, int n, string s){if(k==n){res.push_back(stoi(s));return;}for(int i=0; i<10; i++)dfs(k+1, n, s+to_string(i));}vector<int> countNumbers(int cnt) {for(int i=1; i<=cnt; i++)for(int j=1; j<10; j++)dfs(1, i, to_string(j));return res;} };
五、相关题目
定义一个函数，在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围，我们也要把它当作大数来处理。在第一个思路中，实现了在字符串表示的数字上加 1 的功能，可以参考这个思路实现两个数字的相加功能。另外还有一个需要注意的问题：
如果输入的数字中有负数，我们应该怎么去处理？
通常对于大数问题，常用的方法就是使用字符串来表示这个大数。可以先将两个整数分别用字符串来表示，然后分别将这两个字符串拆分成对应的字符数组。当两个整数都是正数的时候直接相加结果为正数，同为负数的时候取两者的绝对值相加然后在结果前加一个负号。如果是一正一负，则用两者的绝对值相减，用绝对值大的数减去绝对值小的数，当正数的绝对值大的时候相减的结果为正数，当负数的绝对值大的时候相减的结果为负数，结果为负数时在相减的结果前加一个负号即可。在具体进行相加的时候两个字符数组对应的数字字符相加即可，当有进位的时候做出标记，在更高一位进行相加时再将这个进位加进去。
tips：如果面试题是关于 n 位的整数并且没有限定 n 的取值范围，或者是输入任意大小的整数，那么这个题目很有可能是需要考虑大数问题的。字符串是一个简单、有效的表示大数的方法。
