剑指offer | 17. 打印从1到最大的n位数

梦里梦外; 2022-12-26 09:10 114阅读 0赞

**题目内容：**

> 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

**示例 1:**

输入: n = 1
    输出: [1,2,3,4,5,6,7,8,9]

**说明：**

用返回一个整数列表来代替打印
    n 为正整数

--------------------

**方法一：**

*  由观察可以得出，不超过n位数就是指不超过 1 0 n 10^n 10n，比如n=3，那么就是不超过1000.
 *  又因为题干中返回的是int，所以说嘛不会越界，那么最直观的方法应该是可行的：

class Solution { 
    public:
        vector<int> printNumbers(int n) { 
            int c=pow(10,n);
            vector<int> ans;
            if(n==0)return ans;//边界问题不要忘记
            for(int i=1;i<c;i++){ 
                ans.push_back(i);
            }
            return ans;
        }
    };

![在这里插入图片描述][20201204065712634.png]

**方法二：大数法**

*  面试的时候一般不会如此没有坑的题，很可能会出一个int越界之类的，所以我们必须知道如果越界该怎么做？
 *  大数法就是用字符串模拟数字的方法，可以通过将数字转成字符的形式，避免越界问题。假设n=3，那么就是定义一个字符串，初始化成000，然后从1到n进行加减法，最后存到int中循环输出。
 *  字符型`char`转换成数值型`int`，我们可以写成：`int i = c - '0'`
 *  数值型`int`转换成字符型`char`，我们可以写成：`char c = i + '0'`

class Solution { 
    public:
        vector<int> output;
        vector<int> printNumbers(int n) { 
            // 以下注释的前提：假设 n = 3
            if(n <= 0) return vector<int>(0);
            string s(n, '0'); // s最大会等于999，即s的长度为n
            while(!overflow(s)) output.push_back(stoi(s));
            return output;
        }
        bool overflow(string& s)
        { 
            // 本函数用于模拟数字的累加过程，并判断是否越界（即 999 + 1 = 1000，就是越界情况）
            bool isOverFlow = false;
            int carry = 0; // carry表示进位
            for(int i=s.length()-1; i>=0; --i)
            { 
                int current = s[i] - '0' + carry; // current表示当前这次的操作
                if(i == s.length() - 1) current ++; // 如果i此时在个位，current执行 +1 操作
                if(current >= 10)
                { 
                    // 假如i已经在最大的那一位了，而current++之后>=10，说明循环到头了，即999 + 1 = 1000
                    if(i == 0) isOverFlow = true;
                    else
                    { 
                        // 只是普通进位，比如current从9变成10
                        carry = 1;
                        s[i] = current - 10 + '0'; 
                    }
                }
                else
                { 
                    // 如果没有进位，更新s[i]的值，然后直接跳出循环，这样就可以回去执行inputNumbers函数了，即往output里添加元素
                    s[i] = current + '0';
                    break;
                }
            }
            
            return isOverFlow;
        }
    };

*  stoi函数默认要求输入的参数字符串是符合int范围的\[-2147483648, 2147483647\]，否则会runtime error。
 *  atoi函数则不做范围检查，若超过int范围，则显示-2147483648（溢出下界）或者2147483647（溢出上界）。
 *  stoi头文件：,c++函数
 *  atoi头文件:,c函数
 *  atoi()的参数是 const char\* ,因此对于一个字符串str我们必须调用 c\_str()的方法把这个string转换成 const char\*类型的,
 *  而stoi()的参数是const string\*,不需要转化为 const char\*；  
    ![在这里插入图片描述][20201204074034228.png]  
    **方法三：递归全排列**
 *  输出n位数的全排列。

class Solution { 
    public:
        vector<int> output;
        vector<int> printNumbers(int n) { 
            if(n <= 0) return vector<int>(0);
            string s(n, '0');
            for(int i=0; i<=9; ++i)
            { 
                s[0] = i + '0';
                permutation(s, s.length(), 1);
            }
            return output;
        }
        void permutation(string& s, int length, int pos)
        { 
            if(pos == length)
            { 
               inputNumbers(s);
               return; 
            }
            for(int i=0; i<=9; ++i)
            { 
                s[pos] = i + '0';
                permutation(s, length, pos + 1);
            }
        }
        void inputNumbers(string s)
        { 
            bool isUnwantedZero = true;// 判断是否是不需要添加的0，比如001前面的两个0
            string temp = "";
            for(int i=0; i<s.length(); ++i)
            { 
                if(isUnwantedZero && s[i] != '0') isUnwantedZero = false;
                if(!isUnwantedZero) temp += s[i];
            }
            if(temp != "") output.push_back(stoi(temp)); // 如果 s = "000"，则temp会是空，stoi无法执行，会报错
        }
    };

![在这里插入图片描述][20201204084337386.png]

参考：  
[非字节题库 - \#剑17 - 简单 - 打印从1到最大的n位数 - 1刷][- _17 - _ - _1_n_ - 1]  
[atoi()函数和stoi()函数][atoi_stoi]

[20201204065712634.png]: /images/20221120/8338c45afd1c44859a0bc3b9d7986a90.png
[20201204074034228.png]: /images/20221120/7392f45dc70a4fd4a1149579ee24bdd4.png
[20201204084337386.png]: /images/20221120/4af445978cbe41cbbba8af80b3da159d.png
[- _17 - _ - _1_n_ - 1]: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/fei-zi-jie-ti-ku-jian-17-jian-dan-da-yin-cong-1dao/
[atoi_stoi]: https://blog.csdn.net/zrh_CSDN/article/details/80712373?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160703841019725271067443%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160703841019725271067443&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-80712373.pc_first_rank_v2_rank_v28&utm_term=stoi&spm=1018.2118.3001.4449