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

原题链接

题目描述：

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

示例 1：

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

说明：

• 用返回一个整数列表来代替打印
• n 为正整数

一、暴力

题目要求 “按顺序打印出从 1 到最大的 n 位十进制数” ，因此需找出最大的n位数与数字位数n的关系。

不难发现，pow(10, n) - 1 即为最大的n位数，代码自然写出：

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

看一看，效率还不错。

然而，这却是一道各大企业都经常面试考察的题目？怎会如此简单？

没错，leetcode改掉了原题的精髓。

扒一扒原书，

果然，大数才是这题考察的重点，因此很自然的想到了全排列来解决本题。

二、全排列

不妨让我们先忽略leetcode的题目要求，改为返回一个string类型的vector。

固定高位数字，向低位递归数字即可。

注意去除前导零，代码如下：

class Solution {
public:
    vector<string> res;
    string s;
    void per(int n){
        if(n == 0)
        {
            int l = 0;
            while(s[l] == '0')
                l++;
            if(l > s.size() - 1)
                return;
            res.push_back(s.substr(l));
            return ;
        }
        for(int i = 0; i <= 9; i++)
        {
            s += to_string(i);
            per(n - 1);
            s.pop_back();
        }  
    }
    vector<string> printNumbers(int n) {
        per(n);
        return res;
    }
};

为 运行通过 ，稍作更改：

class Solution {
public:
    vector<int> res;
    string s;
    void per(int n){
        if(n == 0)
        {
            int l = 0;
            while(s[l] == '0')
                l++;
            if(l > s.size() - 1)
                return;
            res.push_back(stoi(s.substr(l)));
            return ;
        }
        for(int i = 0; i <= 9; i++)
        {
            s += to_string(i);
            per(n - 1);
            s.pop_back();
        }  
    }
    vector<int> printNumbers(int n) {
        per(n);
        return res;
    }
};

效率从0ms提升到了28ms，不错！(doge)