LeetCode 967. 连续差相同的数字

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
广度优先搜索 回溯

题目描述

✅ 967. 连续差相同的数字

image-20260928225416781

image-20260928225416783

题意分析

返回所有恰好有 n 位、相邻两位数字的差的绝对值都等于 k 的非负整数，结果顺序不限。多位整数不能有前导零，但首位之后允许出现零。

题目保证 2 <= n <= 9、0 <= k <= 9。条件约束每一对相邻数位，不是要求整个数递增，也不是只比较首尾。因为位数至少为二，起始数位只能选择一到九。

解法：按位扩展构造数字

核心思路

[!blue]

一个合法前缀已经满足其内部所有相邻位的条件，追加下一位时，只需要检查新数位与当前末位的差。因此可以从一位数开始，按长度一层一层扩展，而不用枚举全部 n 位整数再筛选。

用 cur 保存当前长度的所有合法前缀，初始为一到九。对每个前缀 num，末位为 last = num % 10，下一位只能是 last + k 或 last - k。保留落在零到九之间的候选，用 num * 10 + digit 把它追加到末尾。

每轮创建独立的 next，只从旧长度的 cur 生成新长度前缀，再用 next 替换 cur。这样处理完长度 level 的一轮后，集合中所有数都恰好是这个位数，不会把同一轮刚生成的更长结果继续扩展。

当 k = 0 时，加减得到同一个下一位，只生成其中一支；当 k > 0 时，两支不同。不同前缀追加数位后也不可能变成同一个整数，因为删除末位就能唯一还原原前缀。因此处理好零差分支后，无需额外集合去重。

任意合法整数都有合法的首位和逐位前缀，且每一步的下一位都属于上述两个候选，所以按层扩展不会漏解。只追加满足差值和数位范围的候选，也保证生成的全部结果合法。

解题步骤

  1. 将一到九加入 cur，表示所有合法的一位前缀。
  2. 让 level 从二增加到 n，每轮创建空 next。
  3. 对每个当前前缀，计算末位，尝试追加不大于九的 last + k。
  4. 若 k != 0 且 last - k >= 0，再追加这一候选，避免零差时重复。
  5. 用 next 替换 cur；构造完 n 位后返回这一层。

代码实现

class Solution {
    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 {
    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})$。
  • 空间复杂度：$O(9\cdot 2^{n-1})$ 上界，同时保存当前层和下一层；实际数量会因数位范围限制而减少。

关键点总结

[!green]

  • 已合法前缀只需检查最后一位与新数位，局部条件即可逐层保证整体合法。
  • 首位不为零与后续位可以为零是不同限制。
  • 独立新层控制位数，k = 0 时只走一支控制重复。

易错点总结

[!yellow]

  • 从零开始构造多位前缀，会产生不合法的前导零数字。
  • 把差的绝对值要求理解成只能加 k，会漏掉允许递减的相邻数位。
  • 不检查候选是否位于零到九，就可能把负数或两位数当作单个数位追加。
  • 零差时仍加入加减两支，会重复生成同一个数字。
  • 把新前缀混入当前集合继续遍历，会失去每层位数一致的保证。

相似题目

题目 难度 关联与区别
1291. 顺次数 中等 原题只允许后一数码比前一数码大1，本题允许上下两个方向且绝对差固定为k。
17. 电话号码的字母组合 中等 同样逐位置枚举合法字符选项，本题下一位选项由前一数码与k决定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/93085311
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！