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

in with 0 comment

剑指 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]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 10 的 n 次方减一,遍历将所有数字放入数组
  2. 大数问题,int 和 long 都会有上限,所以只能使用字符串保存结果。每一个位数的所有结果即为其从 1 - 9 和若干次 0 - 9 的全排列组合,将位数放入循环累加所有结果到字符串中即为最终结果。当第一次开始全排列组合时,舍弃掉从 0 开始的全排列,其他情况都是从 0 开始,解决了 01,02 类似的情况。

代码

解法一

class Solution {
    public int[] printNumbers(int n) {
        int count = (int) Math.pow(10, n) - 1;
        int[] res = new int[count];
        for (int i = 0; i < count; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

解法二

class Solution {
    char[] num, chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    StringBuilder sb = new StringBuilder();

    String printNums(int n) {
        num = new char[n];
        for (int i = 1; i <= n; i++) {
           dfs(0, i);
        }
        return sb.deleteCharAt(sb.lastIndexOf(",")).toString();
    }

    void dfs(int index, int len) {
        if (index == len) {
            sb.append(new String(num).trim() + ",");
            return;
        }
        int start = index == 0 ? 1 : 0;
        for (int i = start; i < chars.length; i++) {
            num[index] = chars[i];
            dfs(index + 1, len);
        }
    }
}