LeetCode 967. 连续差相同的数字

2024-03-04 HGNULB 约 9 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 967. 连续差相同的数字

题意分析

题目要的是把满足条件的整数全部列举出来，而不是数个数：所有恰好 $n$ 位的非负整数中，相邻两位的数字之差绝对值恰好等于 $k$ 的那些，全部返回，顺序不限。

「恰好 $n$ 位」隐含了不允许前导零这条规则，所以最高位只能取 1 到 9。约束里 $n$ 最大 9、$k$ 最大 9，规模非常小；同时输出本身就是一个列表，说明答案数量不会爆炸，这个量级允许我们把每一个合法数字真的构造出来。

约束还有一层是「逐位局部」的：条件只约束相邻的两位，从来不跨位。这意味着一个数字合不合法可以边写边判，不必等到全部写完。

边界上要注意两点：题目保证 $n \geq 2$，所以不存在只有一位的退化情况，不必纠结单独的 0 算不算合法；$k$ 可以取 0，此时相邻两位必须完全相同，「加 $k$」和「减 $k$」会给出同一个候选位，这是唯一需要特殊照顾的取值。

解法：按位扩展构造数字

核心思路

最直接的暴力是把 $n$ 位数的整个区间扫一遍，对每个数逐位检查相邻差。$n = 9$ 时这个区间有九亿个数，显然不可接受；更浪费的是，绝大多数数字在检查第一、第二位时就已经出局，后面七位的检查纯属白做。

瓶颈就在这里：暴力先造出完整的数字再统一验证，而合法性其实在写下第二位的时候就能判定。反过来做，我们不去筛选数字，而是直接生成数字——每次只往已有前缀的末尾添加一位，添加时就保证它和前一位的差恰好为 $k$，这样生成出来的每一个中间结果都是合法前缀，一步废料都没有。

再往下观察一层：一个合法前缀能怎样继续扩展，完全由它的最后一位决定，和前面写了什么毫无关系。因为约束只跨越相邻两位，前缀的历史信息在扩展时是多余的。这让我们可以把同一层的所有前缀混在一起批量处理，不需要记录路径，也不需要回溯撤销。

于是可以写下逐层推进的不变量：进入第 $L$ 轮之前，列表 cur 恰好装着全部「长度为 $L$、无前导零、且内部所有相邻位差均为 $k$」的整数，一个不多一个不少。初始时 $L = 1$，cur 是 1 到 9（无前导零排除了 0），不变量成立；每一轮把 cur 里每个数的末位 $d$ 取出，尝试追加 $d + k$ 和 $d - k$，只保留落在 0 到 9 之内的候选，得到的新列表就是长度 $L + 1$ 的全部合法数字，不变量维持。推到 $L = n$ 时，cur 就是答案。

唯一的例外来自 $k = 0$：此时 $d + k$ 和 $d - k$ 是同一个数字，两条分支会把同一个结果塞进列表两次，破坏「一个不多」。所以 $k = 0$ 时必须只走一条分支。

解题步骤

把 cur 初始化为 1 到 9 这九个一位数。为什么不含 0：0 作为最高位就是前导零，长度为 $n \geq 2$ 的数字不允许以它开头，从源头排除比事后过滤干净。

用一层循环把长度从 2 推到 $n$，每轮开一个新的 next 列表来装扩展结果。为什么要新开列表而不是原地追加：边遍历边往同一个列表里加元素会让本轮的产物在本轮又被扩展一次，层次彻底混乱。

对 cur 中的每个数 num，用 num % 10 取出末位 last。为什么只需要末位：约束只作用于相邻两位，前缀里更早的位对能否扩展没有任何影响。

令 high = last + k，若 high <= 9 则把 num * 10 + high 放进 next。为什么只检查上界：$k$ 和 last 都非负，high 不可能小于 0，下界检查是多余的。

令 low = last - k，若 k != 0 且 low >= 0 则把 num * 10 + low 放进 next。为什么只检查下界：last 不超过 9、$k$ 非负，low 不可能大于 9。为什么要额外挡 k != 0：$k$ 为 0 时 low 和 high 是同一个数字，不挡就会产出重复结果。

每轮结束把 cur 指向 next，循环结束后 cur 中就是全部长度为 $n$ 的答案，转成数组返回。

以 n = 3, k = 7 走一遍：初始 cur = [1, 2, 3, 4, 5, 6, 7, 8, 9]。

第一轮（扩到长度 2）逐个处理：末位 1，high = 8 合法产出 18，low = -6 越界丢弃；末位 2，high = 9 产出 29，low = -5 丢弃；末位 3 到 6，high 分别是 10、11、12、13 全部大于 9，low 分别是 -4、-3、-2、-1 全部小于 0，一个都产不出；末位 7，high = 14 丢弃，low = 0 产出 70；末位 8，high = 15 丢弃，low = 1 产出 81；末位 9，high = 16 丢弃，low = 2 产出 92。本轮结束 cur = [18, 29, 70, 81, 92]。

第二轮（扩到长度 3）：18 的末位是 8，high = 15 丢弃，low = 1 产出 181；29 的末位是 9，high = 16 丢弃，low = 2 产出 292；70 的末位是 0，high = 7 产出 707，low = -7 丢弃；81 的末位是 1，high = 8 产出 818，low = -6 丢弃；92 的末位是 2，high = 9 产出 929，low = -5 丢弃。

长度已达 3，循环结束，返回 [181, 292, 707, 818, 929]。逐个复核：181 的相邻差是 $ 1-8 = 7$ 与 $ 8-1 = 7$，707 的相邻差是 $ 7-0 = 7$ 与 $ 0-7 = 7$，全部符合，且没有任何以 0 开头的数字混进来。

再看 $k = 0$ 的分歧点：若 n = 2, k = 0，第一轮里末位 1 的 high 和 low 都等于 1，靠 k != 0 挡住第二条分支后只产出一个 11，最终得到 11 到 99 共九个数；不挡的话每个数会被产出两次，答案里出现 18 个元素。

代码实现

class Solution {
    // 已经构造出的数字只需要关注最后一位，下一位只能是 last + k 或 last - k。
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> cur = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            cur.add(i);
        }

        for (int level = 2; level <= n; level++) {
            List<Integer> next = new ArrayList<>();
            for (int num : cur) {
                int last = num % 10;
                int high = last + k;
                int low = last - k;

                if (high <= 9) {
                    next.add(num * 10 + high);
                }
                if (k != 0 && low >= 0) {
                    next.add(num * 10 + low);
                }
            }

            cur = next;
        }

        int[] res = new int[cur.size()];
        for (int i = 0; i < cur.size(); i++) {
            res[i] = cur.get(i);
        }
        return res;
    }
}

func numsSameConsecDiff(n int, k int) []int {
    // 已经构造出的数字只需要关注最后一位，下一位只能是 last + k 或 last - k。
    cur := make([]int, 0)
    for i := 1; i <= 9; i++ {
        cur = append(cur, i)
    }

    for level := 2; level <= n; level++ {
        next := make([]int, 0)
        for _, num := range cur {
            last := num % 10
            high := last + k
            low := last - k

            if high <= 9 {
                next = append(next, num*10+high)
            }
            if k != 0 && low >= 0 {
                next = append(next, num*10+low)
            }
        }

        cur = next
    }

    return cur
}

复杂度分析

时间复杂度：$O(9 \cdot 2^{n-1})$，起始有 9 个一位数，之后每扩展一位每个前缀最多分裂成两支（$k = 0$ 时只有一支），每次扩展只做常数次算术，所以总工作量与产出的数字总数同阶；由于 $n \leq 9$，最坏也只有几百个候选。

空间复杂度：$O(9 \cdot 2^{n-1})$，同一时刻要同时持有 cur 和 next 两层结果，规模与答案本身同阶；除此之外没有递归栈，也没有额外的辅助结构。

关键点总结

当约束只作用在相邻元素之间时，「先造完再验证」应当立刻改写成「边造边验证」，把过滤动作前移到每一次扩展，搜索空间会从整个值域塌缩到答案本身的规模。

判断一个前缀能否继续扩展，只需要它的充分统计量。这里的充分统计量就是末位数字，认清这一点之后，同一层的前缀可以批量处理，既不用记录路径也不用回溯。

逐层 BFS 式的构造和 DFS 回溯是等价的两种写法，但逐层写法没有共享可变状态，天然不存在「忘记恢复现场」这一类错误，白板上更稳。

参数的退化取值要单独审一遍。$k = 0$ 让两条本该不同的分支重合，这类「参数取边界值导致分支塌缩」的重复，是构造类题目最常见的失分点。

面试视角：写完后主动说明为什么不需要去重（除了 $k = 0$ 那处），以及为什么最高位从 1 开始——这两句话正好覆盖面试官准备追问的两个点。

面试视角：如果被追问「$n$ 很大怎么办」，可以指出这个构造过程本质是一张十个节点的状态转移图（节点是末位数字，边是差为 $k$ 的转移），求数量时可以用矩阵快速幂把 $n$ 推到很大，但本题要求返回具体数字，输出规模本身就限制了 $n$。

易错点总结

错误写法：不对 $k = 0$ 做特判，两条分支都追加。用例 n = 2, k = 0 → 每个数字被产出两次，返回 [11,11,22,22,...,99,99] 共 18 个元素，正确答案只有 9 个。

错误写法：初始列表从 0 开始，写成 for (int i = 0; i <= 9; i++)。用例 n = 2, k = 1 → 会多出 01 这类带前导零的数字（存成整数后是 1），答案里混进位数不足的值。

错误写法：取末位用 num / 10 而不是 num % 10。用例 n = 3, k = 7 → 第二轮从 18 里取到的是 1 而不是 8，产出 188，而 188 的后两位差是 0，根本不满足条件。

错误写法：上界检查写成 high >= 0（把该管上界的条件写成了管下界）。用例 n = 2, k = 5 → last = 8 时 high = 13 通过检查，拼出 $8 \times 10 + 13 = 93$，得到一个既不满足差值条件、又不是简单拼接的错误数字。

错误写法：层循环写成 for (level = 1; level <= n; level++)。用例 n = 2, k = 1 → 多扩展了一层，返回的全是三位数，长度整体错位。

错误写法：每轮结束忘记把 cur 指向 next。用例任意输入 → 每一轮都在扩展同一批一位数，最终返回的依然是 1 到 9。

错误写法：不新建 next，直接一边遍历 cur 一边往 cur 里追加。用例任意输入 → Java 下遍历时修改集合抛并发修改异常，Go 下则会把本轮新产出的数字在本轮再次扩展，长度彻底失控。

错误写法：套用回溯模板，用一个共享的可变缓冲区拼接数字却不在返回前撤销最后一位。用例任意 $n \geq 3$ 的输入 → 兄弟分支读到上一条分支残留的位，产出的数字既非法又互相污染。

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	每层候选来自固定映射表，分支数随字符变化
22. 括号生成	中等	剪枝依据是左右括号的累计计数而非相邻元素关系
39. 组合总和	中等	同一候选可无限次复用，靠起始下标压制重复方案
90. 子集 II	中等	输入含重复元素，需排序后跳过同层相同值去重