17.打印从1到最大的n位

参考链接

牛客网-剑指Offer

帅地

LeetCode LCR 135.报数

优秀题解

class Solution {
    int[] res;
    int nine = 0, count = 0, start, cnt;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] countNumbers(int cnt) {
        this.cnt = cnt;
        res = new int[(int)Math.pow(10, cnt) - 1];
        num = new char[cnt];
        start = cnt - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if(x == cnt) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(cnt - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solutions/278565/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

start：需要裁切的位数，例如当cnt=3，需要对数组中例如 ‘001’ 下标为2开始裁切

nine：每多加一个‘9’出现时，start就多前进一位，例如 ：

cnt=3，start=2，nine=1, 1~9；

cnt=3，start=1，nine=2, 10~99；

cnt=3，start=0，nine=3, 100~999；