PROBLEM

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

难度 简单

MY ANSWER

题目设置有问题，所以没考虑大数，时间复杂度O(10^n)，空间复杂度O(10^n)。

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        int x = 1;
        x = pow(10, n);
        for(int i = 1; i < x; i++) {
            res.push_back(i);
        }
        return res;
    }
};

BETTER SOLUTION

考虑大数，使用string储存大数，使用递归生成数的字符串，去除前导0后加入string向量中。

#include <iostream>
#include <string>
#include <vector>

using namespace  std;

int n;
vector<string> nums;
vector<string> digit = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};

void printnum(string num) {
    if(num.size() == n) {
        string zero(n, '0');
        if(!zero.compare(num)) {
            return;
        }
        for(int i = 0; i < num.length() ; i++) {
            if(num[i] == '0') {
                num.erase(i, 1);
                i--;
            }
            else {
                break;
            }
        }
        // cout << num <<endl;
        nums.push_back(num);
        return;
    }
    else {
        for(int i = 0; i < 10; i++) {
            printnum(num + digit[i]);
        }
        return;
    }
}

int main() {
    cin >> n;
    for(int i = 0; i < 10; i++) {
        printnum(digit[i]);
    }
    cout << nums.size() << endl;
    for(int i = 0; i < nums.size(); i++) {
        cout << nums[i] << ", ";
    }
}

SUMMARY

注意考虑大数时，使用字符串储存，递归生成自负床，并进行去除前导0。