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

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    常规思路：使用 pow 函数
*/
class Solution {
public:
    vector<int> res;
    
    vector<int> printNumbers(int n) {
        if (n == 0) return res;

        for (int i = 1, max = pow(10, n); i < max; i ++) {
            res.push_back(i);
        }
        return res;
    }
};

/*
    递归，把问题转换成数字排列的解法
*/
class Solution {
public:
    vector<int> res;

    vector<int> printNumbers(int n) {
        if (n == 0) return res;

        string num(n, '0');
        for (int i = 0; i <= 9; i ++) { // 从高位到低位进行全排列
            num[0] = i + '0';
            permutationNums(num, n, 1); // 设置下一位
        }
        return res;
    }

    // 对数字全排列
    void permutationNums(string& num, int length, int index) {
        if (index == length) {
            saveNum(num); // 存储结果
            return;
        }
        for (int i = 0; i <= 9; i ++) {
            num[index] = i + '0'; // 设置第 index 位的字符
            permutationNums(num, length, index + 1);
        }
    }

    // 存储结果：只能存储前导非0的排列
    void saveNum(string num) {
        string tempStr = "";
        bool isBeginZero = true;
        for (int i = 0; i < num.length(); i ++) {
            if (isBeginZero && num[i] != '0') isBeginZero = false;
            if (!isBeginZero) tempStr += num[i];
        }
        // 首字符为 0 时，tempStr 为空，不能执行 stoi
        if (tempStr != "") {
            int tempNum = stoi(tempStr);
            res.push_back(stoi(tempStr));
        }
    }
};

C++ 代码 - leetcode

/*
    常规思路：使用 pow 函数
*/
class Solution {
public:
    vector<int> res;

    vector<int> printNumbers(int n) {
        if (n == 0) return res;

        for (int i = 1, max = pow(10, n); i < max; i ++) {
            res.push_back(i);
        }
        return res;
    }
};

/*
    递归，把问题转换成数字排列的解法
*/
class Solution {
public:
    vector<int> res;

    vector<int> printNumbers(int n) {
        if (n <= 0) return res;

        string num(n, '0');
        for (int i = 0; i <= 9; i ++) // 从高位到低位进行全排列
        {
            num[0] = i + '0';
            permutationNumbers(num, n, 1); // 设置下一位
        }
        return res;
    }

    // 对数字全排列
    void permutationNumbers(string& num, int length, int index) {
        if (index == length) {
            saveNumber(num);
            return;
        }

        for (int i = 0; i <= 9; i ++) 
        {
            num[index] = i + '0'; // 设置第 index 位的字符
            permutationNumbers(num, length, index + 1);
        }
    }

    // 存储结果：只能存储前导非0的排列
    void saveNumber(string num) {
        string str = "";
        bool isBegin0 = true;
        for (int i = 0; i < num.size(); i ++) 
        {
            if (isBegin0 && num[i] != '0') isBegin0 = false;
            if (!isBegin0) str += num[i];
        }
        // 首字符为 0 时，str 为空，不能执行 stoi
        if (str != "") {
            int tempNum = stoi(str);
			res.push_back(stoi(str));
        }
    }
};

/*
    转换为大数问题求解
*/
class Solution {
public:
	vector<int> res;

	vector<int> printNumbers(int n) {
		if (n <= 0) return res;

		string number(n, '0');
		while (!increment(number)) {
			saveNumber(number);
		}
		return res;
	}

	bool increment(string& num) {
        bool isOverflow = false; // 检测是否越界
		int takeOver = 0; // 存储进位
		int length = num.size();
        for (int i = length - 1; i >= 0; i --) 
        {
            int sum = num[i] - '0' + takeOver;
            if (i == length - 1) sum ++;
            if (sum >= 10) // 有进位
            {
                if (i == 0) // 最高位有进位，超过了给定的最大值，越界
                {
                    isOverflow = true;
                }
                else 
                {
                    takeOver = 1;
                    num[i] = sum - 10 + '0';
                }
            }
            else // 没有进位
            {
                num[i] = sum + '0';
				break;
            }
        }
        return isOverflow;
    }

	void saveNumber(string num) {
		string str = "";
        bool isBeginZero = true;
        string::iterator iter = num.begin();
        while (iter != num.end())
        {
            if (isBeginZero && *iter != '0') isBeginZero = false;
            if (!isBeginZero) str += *iter;
            iter ++;
        }
		int t = stoi(str);
        res.push_back(t);
	}
};