题解 | 打印从1到最大的n位数

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 最大位数
     * @return int整型vector
     */

    bool Increment(std::string& number) { // &，要修改
        bool isOverflow = false;
        int carry = 1;
        for (int i = number.length() - 1; i >= 0; --i) {
            int sum = (int)(number[i] - '0') + carry;
            if (sum >= 10) {
                if (i == 0)
                    isOverflow = true;
                else {
                    sum -= 10;
                    number[i] = '0' + sum;
                }
            } else {
                // 没有进位就直接退出，前面的保持不变
                number[i] = '0' + sum;
                break;
            }
        }
        return isOverflow;
    }

    int PrintNumber(const std::string& number){
        if(number.empty()) return 0;
        bool firstZero = true;
        int ans = 0;
        for(int i = 0; i < number.size(); ++i){
            if(firstZero&&number[i]=='0')   continue;
            else{
                firstZero = false;
                ans = std::stoi(number.substr(i));
                break;
            }
        }
        return ans;
    }
    vector<int> printNumbers(int n) {
        // write code here
        vector<int> res;
        if (n <= 0)
            return res; // 说明输入错误了，我们可以throw一个异常或者全局变量
        std::string str(n, '0');
        while (!Increment(str)) {
            res.push_back(PrintNumber(str));
        }
        return res;
    }
};

因为返回是int的vector，所以其实可以不考虑大数问题了。

这里给了一种大数的解法，再转化成int以满足这道题的输出。

大数问题一般通过字符串解决，只让最后一位加，然后依次看进位。

dfs大数做法：

#include <string>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 最大位数
     * @return int整型vector
     */
    
    int my_stoi(string str){
        if(str.empty()) return 0;//错误
        int ans = 0;
        for(int i = 0; i < str.length(); ++i){
            if(str[i]=='0') continue;
            else{
                ans = std::stoi(str.substr(i));
                break;
            }
        }
        return ans;
    }
    void dfs(int n, string& cnt, vector<int>& res){
        if(n==cnt.size()){//最后一个下一个来输出，最后一个还是要遍历0-9的
            int temp = my_stoi(cnt);
            if(temp!=0)//0不要，00之类也不要，但是多0情况我的my_stoi()输出依然是0，所以可以这样判断
                res.push_back(temp);
            return;
        }
        for(int i = 0; i < 10; ++i){
            cnt[n] = '0' + i;
            dfs(n+1, cnt, res);
        }
    }
    vector<int> printNumbers(int n) {
        // write code here
        vector<int> res;
        if(n<=0) return res;//最好throw点什么
        string cnt(n, '0');
        dfs(0, cnt, res);
        return res;
    }
};

对于这道题因为是输出所有值，所以还可以用递归遍历。

dfs要注意stoi不能用于空字符串。