17.打印从 1 到最大的 n 位数 (Easy)*

题目描述*

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

示例*

输入: n = 1

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

代码*

直接从 1 输出到 pow(10, n)，过于傻逼。

虽然这个题返回的是 vector，注定不会溢出，但还是练习一下大数处理，甚至可以用全排列做。

字符串存大数的话还是要练一下 char 数组，总用 string 感觉不太行。

字符串数组存大数的效率不高，感觉可以直接用数组存，unsigned int 数组，2^32 进制。

char 数组string 大数递归全排列

class Solution {
private:
    bool strInc(char *number) {
        bool isOverflow = false;
        // 进位标志
        bool nTakeOver = 0;
        int len = strlen(number);
        for(int i = len - 1; i >= 0; i--) {
            int sum = number[i] - '0' + nTakeOver;
            // 实现 +1，从末位开始加
            if(i == len - 1) {
                sum += 1;
            }
            if(sum >= 10) {
                // 最高位进位，溢出
                if(i == 0) {
                    isOverflow = true;
                }else {
                    sum -= 10;
                    nTakeOver = 1;
                    number[i] = '0' + sum;
                }
            }else {
                number[i] = '0' + sum;
                break;
            }
        }
        return isOverflow;
    }
    void printStrToNum(char *number, vector<int> &res) {
        // 跳过字符串开头的 0
        while(*number == '0') {
            number++;
        }
        res.push_back(atoi(number));
    }
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        if(n <= 0) {
            return res;
        }
        // 按照剑指 offer 上的 char 数组处理方法。
        char *number = new char[n + 1];
        memset(number, '0', n);
        number[n] = '\0';
        while(!strInc(number)) {
            printStrToNum(number, res);
        }
        delete []number;
        return res;
    }
};

class Solution {
private:
    bool strInc(string& number) {
        bool isOverflow = false;
        int nTakeOver = 0;
        int len = number.length();
        for(int i = len - 1; i >= 0; i--) {
            int sum = number[i] - '0' + nTakeOver;
            if(i == len - 1) {
                sum += 1;
            }
            if(sum >= 10) {
                if(i == 0) {
                    isOverflow = true;
                }else {
                    nTakeOver = 1;
                    number[i] = sum - 10 + '0';
                }
            } else {
                number[i] = '0' + sum;
                break;
            }
        }
        return isOverflow;
    }
    void printStrToNum(string number, vector<int>& res) {
        res.push_back(stoi(number));
    }
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        if(n <= 0) {
            return res;
        }
        string number(n, '0');
        while(!strInc(number)) {
            printStrToNum(number, res);
        }
        return res;
    }
};

class Solution {
private:
    vector<int> res;
    void permute(string& number, int len, int index) {
        if(index == len) {
            res.push_back(stoi(number));
            return;
        }
        for(int i = 0; i < 10; i++) {
            number[index] = i + '0';
            permute(number, len, index + 1);
        }
    }
public:
    vector<int> printNumbers(int n) {
        if(n <= 0) {
            return res;
        }
        string number(n, '0');
        for(int i = 0; i < 10; i++) {
            number[0] = i + '0';
            permute(number, n, 1);
        }
        return vector<int>(res.begin() + 1, res.end());
    }
};

最后更新: July 23, 2022