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

难度: 🌕🌗

问题描述

---

解法 1

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

---

输出 1

---

解法 2 - 大数问题

class Solution {
    int[] res;
    int curIndex = 0;
    public int[] printNumbers(int n) {
        // 思路：
        // 若是 n 超出了 long 的范围，此时，就不能直接使用 long，而是需要将其转换为字符串计算
        int len = (int)Math.pow(10, n) - 1; // 这里如果是大数，那么，也无法通过 int 得到，这里只是假设
        res = new int[len];
        for(int i = 1; i <= n; i ++) {
            // 首位只能是 1-9，而不能是 0，所以单独提出来
            for(char j = '1'; j <= '9'; j ++) {
                StringBuilder sb = new StringBuilder();
                sb.append(j);
                mySol(i, 1, sb);
            }
        }
        return res;
    }

    private void mySol(int len, int index, StringBuilder sb) {
        // 递归终止条件
        if(index == len) {
            // 添加到结果集中
            res[curIndex] = Integer.parseInt(sb.toString());
            curIndex ++;
            return;
        }
        for(char i = '0'; i <= '9'; i ++) {
            sb.append(i);
            mySol(len, index + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

输出 2