题目

题解

这道题如果不考虑大数的话很简单，但是原书主要是解决输出大数的问题，因此大数也要加以练习（leetcode不考虑大树也能通过）

1. 普通解法

最普通的解法，就是先算上限，然后挨个输出，这种答案不严谨的。

  • 时间复杂度$O(10^{n})$
  • 空间复杂度$O(10^{n})$
class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        if(n==0) return res;
        for(int i=1, k=pow(10,n); i<k; ++i){
            res.push_back(i);
        }
        return res;
    }
};

2. char法（书上的）

用char辅助递增和打印数组。下面的几个方法主要是解决大数的问题，即不使用变量存值，而是用string或者char存值挨个输出数字 char的方法见(https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/c-3chong-jie-fa-by-xdb/)

3. string法（书上的改为用string）

class Solution {
    vector<int> res;
public:
    bool Increment(string& number){
        bool isOverflow = false;//判断是否溢出
        int takeOver = 0;//进位位
        for(int i=number.size()-1; i>=0; --i){
            int nSum = number[i] - '0' + takeOver;//每一位先计算出其加上进位后的值
            if(i == number.size()-1) nSum++;//最低为加1
            if(nSum >= 10){
                if(i==0) isOverflow = true;//最高位有进位，溢出位置true
                else{//非最高位有进位，改变这个数位当前累加和-10，再把进位位置true
                    number[i] = nSum - 10 + '0';
                    takeOver = 1;
                }
            }else{
                number[i] = nSum + '0';
                break;//如果没有进位，那么改变完最后一个有进位的数就可以跳出循环。高位的数不需要改变
            }
        }
        return isOverflow;
    }
////两种savenumber的写法，第二种更简洁
    // void saveNumber(string number){
    //     string new_number;
    //     bool isBegin0 = true;
    //     for(auto& n: number){
    //         if(isBegin0 && n != '0') isBegin0 = false;
    //         if(!isBegin0){
    //             new_number.push_back(n);
    //         }
    //     }
    //     //对于本题以上都没用，上面是用来去掉前面的0的
    //     int num = stoi(new_number);
    //     res.emplace_back(num);
    // }

    void saveNumber(const string& number)
	{
		auto index = number.find_first_not_of('0');//找到第一个不0的字符小标
		if(index!=string::npos)//若全为0则返回string::npos
			res.push_back(stoi(number.substr(index)));
	}


    vector<int> printNumbers(int n) {
        if(n==0) return res;
        string number(n,'0');//初始化number，n个0
        while(!Increment(number)){
            saveNumber(number);
        }
        return res;
    }
};

4. 递归法

class Solution {//四种方法。4.递归
    vector<int> res;
public:
    void permutation(string& number, int length, int index){
        if(index == length){
            saveNumber(number);
            return;
        }//当index超出界限，就在res中保存，并返回
        //没超出，就不断递归，每一位index有十个数i
        for(int i=0; i<10; ++i){
            number[index] = i + '0';//这一步是给当前位赋值
            permutation(number, length, index+1);//然后递归下一位
        }
    }
    void saveNumber(string& number){
        //这是为了跳过0这个数，当其全为0的时候不save
        string tmp_number(number.size(), '0');
        if(tmp_number != number){
            res.push_back(stoi(number));
        }
    }

    vector<int> printNumbers(int n) {
        if(n==0) return res;
        string number(n,'0');//初始化number，n个0
        permutation(number, n, 0);//调用递归函数进行全排列
        return res;
    }
};