【重点】【回溯】【大数】剑指 Offer17：打印从1到最大的n位数

力扣
力扣中描述简单了，本质是考察大数算法。

1.大数 + 全排列

Python

class Solution:
    def countNumbers(self, cnt: int) -> List[int]:
        num_arr = list("0123456789")
        res = list()
        tmp = list()
        for l in range(1, cnt+1):
            self.dfs(0, l, num_arr, res, tmp)
        
        return [int(x) for x in res]

    def dfs(self, start, length, num_arr, res, tmp):
        if start == length:
            res.append(''.join(tmp))
            return
        val = 1 if start == 0 else 0 # 起始索引
        for k in range(val, 10):
            tmp.append(num_arr[k])
            self.dfs(start+1, length, num_arr, res, tmp)
            tmp.pop()

Java

class Solution {
    public int[] countNumbers(int cnt) {
        char[] numArray = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
        StringBuffer tmp = new StringBuffer();
        List<String> res = new ArrayList<>();
        for (int len = 1; len <= cnt; ++len) {
            dfs(0, len, numArray, res, tmp); // 获取长度为len的所有整数
        }
        int[] resArray = new int[res.size()];
        for (int i = 0; i < res.size(); ++i) {
            resArray[i] = Integer.parseInt(res.get(i));
        }

        return resArray;
    }

    public void dfs(int startIndex, int length, char[] numArray, List<String> res, StringBuffer tmp) {
        if (startIndex == length) {
            res.add(tmp.toString());
            return;
        }
        int val = startIndex == 0 ? 1 : 0;
        for (int k = val; k < 10; ++k) {
            tmp.append(numArray[k]);
            dfs(startIndex + 1, length, numArray, res, tmp);
            tmp.deleteCharAt(startIndex);
        }
    }
}

相同思路，py重写！

class Solution:
    def countNumbers(self, cnt: int) -> List[int]:
        num_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
        num = list()
        res_str = list()
        for cur_len in range(1, cnt + 1):
            self.dfs(0, cur_len, num_list, res_str, num)
        res_int = [int(x) for x in res_str]
        return res_int
    
    def dfs(self, startIdx: int, length: int, num_list: list, res_str: list, num: list):
        if startIdx == length:
            res_str.append(''.join(num))
            return
        val = 0
        if startIdx == 0:
            val = 1
        for k in range(val, 10):
            num.append(str(num_list[k]))
            self.dfs(startIdx + 1, length, num_list, res_str, num)
            num.pop()

2.暴力遍历

// 版本1
class Solution {
    public int[] countNumbers(int cnt) {
        int end = (int)Math.pow(10, cnt) - 1;
        int[] res = new int[end];
        for(int i = 0; i < end; i++)
            res[i] = i + 1;
        return res;
    }
}

// 版本2
class Solution {
    public int[] countNumbers(int cnt) {
        List<Integer> res = new ArrayList<>();
        long max = pow(10, cnt) - 1;
        for (int i = 1; i <= max; ++i) {
            res.add(i);
        }
        int[] array = new int[res.size()];
        for (int i = 0; i < res.size(); ++i) {
            array[i] = res.get(i);
        }

        return array;
    }

    public long pow(int x, int n) {
        long res = 1;
        while (n > 0) {
            res *= x;
            --n;
        }

        return res;
    }
}