LeetCode 386. 字典序排数

Categories:

题目描述
思路分析
1. 解法一：按字典序迭代构造（推荐）
相似题目

题目描述

✅ 386. 字典序排数

思路分析

解法一：按字典序迭代构造（推荐）

核心思路：

从 1 开始依次生成下一个字典序数字。

若 cur * 10 <= n，优先进入子节点；否则回溯到能加一的位置。

该过程等价于先序遍历一棵 10 叉树。

复杂度分析：

时间复杂度：O(n)，生成 n 个数字。

空间复杂度：O(1)，仅使用常数变量。

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        int cur = 1;

        // 按字典序依次生成
        for (int i = 0; i < n; i++) {
            ans.add(cur);
            if (cur * 10 <= n) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }

        return ans;
    }
}

func lexicalOrder(n int) []int {
    ans := make([]int, 0, n)
    cur := 1

    // 按字典序依次生成
    for i := 0; i < n; i++ {
        ans = append(ans, cur)
        if cur*10 <= n {
            cur *= 10
        } else {
            for cur%10 == 9 || cur+1 > n {
                cur /= 10
            }
            cur++
        }
    }

    return ans
}

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	DFS
31. 下一个排列	中等	迭代构造
93. 复原 IP 地址	中等	回溯
440. 字典序的第 K 小数字	困难	字典序
78. 子集	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/39470775