【LeetCode-字符串】打印从1到最大的n位数

题目描述

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

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

题目链接： https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

思路

使用大数加法。代码如下：

class Solution {
public:
    vector<int> printNumbers(int n) {
        if(n==0) return {};

        vector<int> ans;
        n = pow(10, n);
        string cur = "0";
        for(int i=1; i<n; i++){
            cur = add(cur, "1");
            ans.push_back(stoi(cur));
        }
        return ans;
    }

    string add(string cur, string one){
        int carry = 0;
        int i = cur.size()-1;
        int j = one.size()-1;
        string sum = "";
        while(i>=0 || j>=0){
            int x = i>=0? cur[i--]-'0':0;
            int y = j>=0? one[j--]-'0':0;
            int s = x+y+carry;
            carry = s/10;
            sum = to_string(s%10)+sum;
        }
        if(carry!=0) sum = "1" + sum;
        return sum;
    }
};

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)