【面试题17 打印从1到最大的n位数】
难度： 简单（其实一点儿也不简单）
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
Leetcode题目对应位置： 面试题17：打印从1到最大的n位数
陷阱： 包含大数问题，即如果 n 很大，很可能会出现溢出，所以不能用循环直接求最大的数字然后循环打印。
如果面试题是关于 n 位的整数且不限定 n 的取值范围，或者输入任意大小的整数，那么就很可能是考察大数问题的。通常大数问题用字符串是一种简单、有效的表示方法。
像这样的就是没有考虑大数问题，简单地循环输出，肯定达不到面试要求：
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> res;
if (n == 0) return res;
// 添加到数组
for (int i = 1, max = pow(10, n); i < max; i++){
res.push_back(i);
}
return res;
}
};
（这道题就不用 Python 写了，只用 C++）
思路 1：字符串模拟大数
用字符串表示数字：每个字符都是‘0’ ~ ‘9’ 之间的某一个字符，用于表示一位数字。对于 n 位的数字，需要长度为 n+1 的字符串（因为最后有一个结束符 \0）。当实际数字不够 n 位时，在字符串前半部分补 0。
首先将字符串中的每一个数字都初始化为 ‘0’，然后每次给字符串表示的数字加 1，再打印。即：1）在字符串表示的数字上模拟加法；2）把字符串表达的数字打印出来。
代码逻辑：
- 确定何时停止对字符串模拟加1：对于 n 位数，停止加 1 的时机应当是字符串的第 1 个字符（下标为 0）产生了进位。如果采用常规的字符串比较法，与长度为 n 的字符串
‘99...99’比较，那么时间复杂度为 O(n)，而判断进位只需要 O(1) - 打印字符串表示的数字：由于字符串长度是固定的，对于不够位数的数字前面位均用 ‘0’ 来补，但打印时数字 98 打印成 0098 就不太合适，不符合阅读习惯，所以要跳过前 m 个为 ‘0’ 的字符，从第一个不为 ‘0’ 的字符开始打印，直到字符串的结尾
class Solution {
public:
vector<int> res;
vector<int> printNumbers(int n) {
if (n <= 0) return res;
//能容纳最大值的字符数组,由于要存储结束符'\0'，因此n要加1
char* number = new char[n + 1];
//初始化字符数组，除最后一个字符外，所有位置均为‘0’
memset(number, '0', n);
number[n] = '\0';
//判断是否最高位进位，否则打印
while (!Increment(number))
{
PrintNumber(number);
}
//注意释放内存
delete[]number;
return res;
}
/*判断最高位是否进位*/
bool Increment(char* number) {
bool isOverflow = false; //越界标识
int nTakeOver = 0; //存储进位
int nLength = strlen(number); //不包含结束符
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTakeOver;
//最低位加1
if (i == nLength - 1)
{
nSum++;
}
if (nSum >= 10) //有进位
{
if (i == 0){ // 最高位有进位，判越界
isOverflow = true;
}
else{ //非最高位有进位
nTakeOver = 1;
number[i] = nSum - 10 + '0'; //计算进位后的第i位
}
}
else //无进位，计算第i位并跳出
{
number[i] = nSum + '0';
break;
}
}
return isOverflow;
}
/*打印字符串模拟的数字*/
void PrintNumber(char* number)
{
string s = "";
bool isBegin0 = true;
while (*number != '\0')
{
//判断当前位是否为需要舍弃的‘0’，否则置isBegin0为false
if (isBegin0 && *number != '0') isBegin0 = false;
if (!isBegin0)
{
s += *number;
}
number++;
}
int num = stoi(s); //str转int
res.push_back(num);
}
};
其他知识点总结：
memset 函数：将指针 ptr 指向的数据的前 num 位用 value 填充。参考 memset( void * ptr, int value, size_t num )- 将数字字符转换为对应的数字：比如将字符 ‘8’ 转换为数字 8，只需要用字符 ‘8’ 减去字符 ‘0’ 即可，因为字符之间的相减其实是 ASCII 码相减
.push_back：在 vector 最后加一个新的值，类似于 Python 的append。参考 void push_back (const value_type& val);stoi：将 str 转换为 int，参考：int stoi (const string& str, size_t* idx = 0, int base = 10);- 注意
s += *number;这一步，由于标准库中重载了 string 和 char 类型的 + 操作，所以可以直接用 + 拼接字符串
思路 2：数字全排列
对于一个 n 位的数字，从 0 到最大的 99…99 实际上就是 n 个从 0 到 9 的全排列，在打印时，将前面的 0 都省去不打印即可。
class Solution
{
public:
vector<int> res;
vector<int> printNumbers(int n) {
if (n <= 0) return res;
char* number = new char[n+1];
memset(number, '0', n);
number[n] = '\0';
//全排列
for (int i = 0; i <= 9; i++)
{
number[0] = i + '0'; //首字符赋初值
permutationNumbers(number, n, 1);//设置下一位
}
return res;
}
/*全排列*/
void permutationNumbers(char* number, int length, int index) {
if (index == length) { //递归边界
saveNumber(number); //存储结果
return;
}
for (int i = 0; i <= 9; i++)
{
number[index] = '0' + i; //设置第index位的字符
permutationNumbers(number, length, index + 1);
}
}
/*存储结果*/
void saveNumber(char* number)
{
string s = "";
bool isBegin0 = true;
while (*number != '\0')
{
//判断当前位是否为需要舍弃的‘0’，否则置isBegin0为false
if (isBegin0 && *number != '0') isBegin0 = false;
if (!isBegin0)
{
s += *number;
}
number++;
}
//排除全为0的情况
if (s != ""){
int num = stoi(s); //str转int
res.push_back(num);
}
}
};
需要特别注意的是，全排列方法会有 0000 这种情况存在，此时对应的数字是 0，不予打印输出，所以字符串 s 会为空，直接使用 stoi 会报错，所以需要先判断一下 s 是否为空。
优化内存
char 类型的字符数组存储实际还有有空间浪费，考虑用 string 存储，在空间上利用率更高。
class Solution {
public:
vector<int> res;
vector<int> printNumbers(int n) {
if (n <= 0) return res;
//初始化字符数组
string number(n, '0');
while (!Increment(number))
{
saveNumber(number);
}
return res;
}
bool Increment(string& number) { //引用传递
bool isOverflow = false;
int nTakeOver = 0;
int nLength = number.size();
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTakeOver;
if (i == nLength - 1){
nSum++;
}
if (nSum >= 10)
{
if (i == 0){
isOverflow = true;
}
else{
nTakeOver = 1;
number[i] = nSum - 10 + '0';
}
}
else{
number[i] = nSum + '0';
break;
}
}
return isOverflow;
}
void saveNumber(string number)
{
string s = "";
bool isBegin0 = true;
string::iterator it = number.begin();
while (it != number.end())
{
if (isBegin0 && *it != '0') isBegin0 = false;
if (!isBegin0)
{
s += *it;
}
it++;
}
int num = stoi(s);
res.push_back(num);
}
};
参考资料：
[1] 剑指 offer 第二版
[2] LeetCode 面试题17：打印从1到最大的n位数
[3] 参考题解
转载：https://blog.csdn.net/qq_31347869/article/details/106123509
查看评论