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

in with 1 comment

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

原题不难,这里需要考虑大数字以及大数字去零的问题

public class App {

    StringBuilder res; // 接受结果
    int n; // 最大值的位数
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; // num是用来生成每一位数字,loop是用来全排列的

    public String printNums(int n) {
        this.n = n;
        res = new StringBuilder();
        num = new char[n]; // 这里 num 就可以确定长度了
        dfs(0); // 进入递归
        res.deleteCharAt(res.length() - 1); // 去除最后一个逗号
        return res.toString();
    }

    private void dfs(int x) {
        if (x == n) { // 用于退出递归和拼接每一个数字
            int i = 0;
            while (i < n && num[i] == '0') {
                i++;
            }
            if (i == n) return; // 全为0,直接跳过
            res.append(String.valueOf(num, i, n - i) + ","); // String.valueOf 三参中的 offset 为上面循环取到以 0 开始的位置,通过该方法可以把 0 全部删除
            return;
        }

        for (char i : loop) {
            num[x] = i; // 将 i 赋值给每个数字的第 x 位
            dfs(x + 1); // 继续给下一位数字赋值
        }
    }

    public static void main(String[] args) {
        System.out.println(new App().printNums(3));
    }
}