LeetCode 967. 连续差相同的数字

Categories:

题目描述
思路分析
1. 解法一：BFS 构造（推荐）
相似题目

题目描述

✅ 967. 连续差相同的数字

思路分析

解法一：BFS 构造（推荐）

核心思路：

以 1~9 作为起点，逐层拼接下一位。

若末位为 d，下一位可为 d+k 或 d-k（需在 0~9 内）。

生成长度为 n 的所有数字。

复杂度分析：

时间复杂度：O(9 * 2^{n-1})，其中 n 表示数字长度。

空间复杂度：O(9 * 2^{n-1})，用于队列与结果。

import java.util.ArrayList;
import java.util.List;

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 d = num % 10;
                int a = d + k;
                int b = d - k;
                if (a >= 0 && a <= 9) {
                    next.add(num * 10 + a);
                }
                if (k != 0 && b >= 0 && b <= 9) {
                    next.add(num * 10 + b);
                }
            }
            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 {
			d := num % 10
			a := d + k
			b := d - k
			if a >= 0 && a <= 9 {
				next = append(next, num*10+a)
			}
			if k != 0 && b >= 0 && b <= 9 {
				next = append(next, num*10+b)
			}
		}
		cur = next
	}

	return cur
}

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	回溯
401. 二进制手表	简单	回溯
784. 字母大小写全排列	中等	回溯
1291. 顺次数	中等	枚举
77. 组合	中等	回溯

本文作者: HGNULB

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