剑指 Offer 17 打印从1到最大的n位数

概述

https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

不考虑溢出的解法

这道题本来应该是想考察溢出的？既然是直接返回向量，那肯定不用关心溢出的事情了。

class Solution {
public:
    vector<int> printNumbers(int n) {
        n--;
        int maxNum = 9;
        while (n--) {
            maxNum *= 10;
            maxNum += 9;
        }
        vector<int> ans;
        for (int i = 1; i <= maxNum; i ++) ans.push_back(i);
        return ans;
    }
};

考虑到溢出的解法

使用字符串表示数字，我们需要处理加法和进位。

另外要注意，由于我们的起始值为 0，所以我们还需要在最终结果中弹出该项。

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<string> ans;
        string s(n, '0');
        while (true) {
            ans.push_back(s);
            if (s[n-1] != '9') {
                s[n-1] ++;
                continue;
            }
            int carry = n - 1;
            while (carry >= 0 && s[carry] == '9') {
                s[carry] = '0';
                carry --;
            }
            if (carry == -1) break;
            s[carry] ++;
        }
        vector<int> res;
        bool flag = true;
        for (auto& s : ans) {
            if (flag) {
                flag = false;
                continue;
            }
            res.push_back(stoi(s));
        }
        return res;
    }
};

Links: sword-offer-17

未经允许，禁止转载，本文源站链接：https://iamazing.cn/