🌕🌕 386. 字典序排数

难度: 🌕🌕

问题描述

---

解法 1 - 递归

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        // 思路：
        // 可以看作多叉树，每一层有 0-9 种选择
        // 先序遍历结果即为字典序
        // 最多有 5 层，因此可以看作 O(1) 空间复杂度
        for(int i = 1; i <= 9; i ++) {
            mySol(i, n);
        }
        return res;
    }

    private void mySol(int left, int right) {
        // 递归终止条件
        if(left > right) {
            return;
        }
        // left <= right
        res.add(left);
        // 继续往下一层寻找
        left *= 10;
        for(int i = 0; i <= 9; i ++) {
            mySol(left + i, right);
        }
    }
}

---

输出 1

---

解法 2 - 迭代

class Solution {
    public List<Integer> lexicalOrder(int n) {
        // 思路：
        // 迭代
        // 假设当前值为 cur，下一次尝试添加 cur * 10，如果 cur*10 不满足要求，尝试添加 cur + 1，
        // 直到 cur 最低为为 9，返回上一层，即 cur /= 10
        // 每次循环变更一次 cur 的状态，因此一共需要循环 n 次
        ArrayList<Integer> res = new ArrayList<>();
        int cur = 1;
        for(int i = 1; i <= n; i ++) {
            res.add(cur);
            // 获取 cur 的下一个有效状态
            if(cur * 10 <= n) {
                cur *= 10; // 尝试在 cur 后面添加 0
            } else {
                // cur 已经是最底层了，无法继续到下一层
                // 尝试在当前层找下一个节点，如果当前层不存在下一个节点，继续往上一层找
                while(cur % 10 == 9 || cur >= n) {
                    cur /= 10; // 直到上面的某个层并不是最后一个节点
                }
                cur ++;
            }
        }
        return res;
    }
}

---

输出 2