LeetCode 967中等回溯 · 枚举
连续差相同的数字 图解题解
这道题到底在问什么
返回所有长度为 n、且每两个相邻位数字差的绝对值都等于 k 的非负整数。除数字 0 本身外不能有前导零。
- 输入
- n = 3, k = 7
- 输出
- [181, 292, 707, 818, 929]
最优解：一步一步想明白
- 3记住这套「定起头、每位只 ±k、越界就剪、满 n 位收一个」，下面每一帧都在套它。
- 4上面一排是 0 到 9 十个数字，每一位都从这里挑。下面 path 是正在拼的数。规矩：除第一位外，每一位都等于上一位加 k 或减 k，且必须落在 0 到 9 里。这道题 n = 3、k = 7。
- 5第一位从 1 开始。开头只能选 1 到 9，不能用 0，否则就成了前导零。path 现在是 [1]，接着往下看下一位。
- 6末位是 1：加 7 得 8，没超过 9，放下去；减 7 会得 -6，是负数，那支不通。path 变成 [1, 8]。
- 7末位是 8：加 7 得 15，超过 9 了先剪掉；减 7 得 1，合法，放下去。path 变成 [1, 8, 1]。
- 8又凑齐三位，[1, 8, 1] 就是 181，相邻差都是 7，收进结果区。
- 9回到最前面，第一位换成 2，重新往下拼。path 现在是 [2]。
- 10末位是 2：加 7 得 9，没超过 9，放下去；减 7 会得 -5，是负数，那支不通。path 变成 [2, 9]。
- 11末位是 9：加 7 得 16，超过 9 了先剪掉；减 7 得 2，合法，放下去。path 变成 [2, 9, 2]。
- 12又凑齐三位，[2, 9, 2] 就是 292，相邻差都是 7，收进结果区。
- 13第一位试 3：加 7 得 10 越界，减 7 得 -4 是负数，两边都迈不出去，这个起头作废，换下一个。
- 14第一位试 4：加 7 得 11 越界，减 7 得 -3 是负数，两边都迈不出去，这个起头作废，换下一个。
- 15第一位试 5：加 7 得 12 越界，减 7 得 -2 是负数，两边都迈不出去，这个起头作废，换下一个。
- 16第一位试 6：加 7 得 13 越界，减 7 得 -1 是负数，两边都迈不出去，这个起头作废，换下一个。
- 17回到最前面，第一位换成 7，重新往下拼。path 现在是 [7]。
- 18末位是 7：加 7 得 14，超过 9 了先剪掉；减 7 得 0，合法，放下去。path 变成 [7, 0]。
- 19末位是 0：加 7 得 7，没超过 9，放下去；减 7 会得 -7，是负数，那支不通。path 变成 [7, 0, 7]。
- 20三位凑齐了，[7, 0, 7] 连起来就是 707，相邻两位差都正好 7，合格，收进右边结果区。
- 21回到最前面，第一位换成 8，重新往下拼。path 现在是 [8]。
- 22末位是 8：加 7 得 15，超过 9 了先剪掉；减 7 得 1，合法，放下去。path 变成 [8, 1]。
- 23末位是 1：加 7 得 8，没超过 9，放下去；减 7 会得 -6，是负数，那支不通。path 变成 [8, 1, 8]。
- 24三位凑齐了，[8, 1, 8] 连起来就是 818，相邻两位差都正好 7，合格，收进右边结果区。
- 25回到最前面，第一位换成 9，重新往下拼。path 现在是 [9]。
- 26末位是 9：加 7 得 16，超过 9 了先剪掉；减 7 得 2，合法，放下去。path 变成 [9, 2]。
- 27末位是 2：加 7 得 9，没超过 9，放下去；减 7 会得 -5，是负数，那支不通。path 变成 [9, 2, 9]。
- 28三位凑齐了，[9, 2, 9] 连起来就是 929，相邻两位差都正好 7，合格，收进右边结果区。
- 29九个起头全试完，合法的数依次是 181、292、707、818、929，一共 5 个，这就是答案。
⚠️ 容易写错的地方
✗ 错：k 等于 0 时加 k、减 k 两支都走
✓ 对：k 等于 0 只走一支
加 0 和减 0 是同一个数字，两支会生成完全重复的数
✗ 错：第一位允许填 0
✓ 对：第一位只从 1 到 9 起头
除数字 0 本身外，前导零不合法，比如 070 是无效的
✗ 错：候选不判越界就直接放
✓ 对：末位 ±k 必须落在 0 到 9 才放
超过 9 或小于 0 都不是一位合法数字，必须当场剪掉
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
def dfs(x: int):
if x >= boundary:
ans.append(x)
return
last = x % 10
if last + k <= 9:
dfs(x * 10 + last + k)
if last - k >= 0 and k != 0:
dfs(x * 10 + last - k)
ans = []
boundary = 10 ** (n - 1)
for i in range(1, 10):
dfs(i)
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
vector<int> ans;
int boundary = pow(10, n - 1);
function<void(int)> dfs = [&]( int x ) {
if (x >= boundary) {
ans.push_back(x);
return;
}
int last = x % 10;
if (last + k < 10) {
dfs(x * 10 + last + k);
}
if (k != 0 && last - k >= 0) {
dfs(x * 10 + last - k);
}
};
for (int i = 1; i < 10; ++i) {
dfs(i);
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private List<Integer> ans = new ArrayList<>();
private int boundary;
private int k;
public int[] numsSameConsecDiff(int n, int k) {
this.k = k;
boundary = (int) Math.pow(10, n - 1);
for (int i = 1; i < 10; ++i) {
dfs(i);
}
return ans.stream().mapToInt(i -> i).toArray();
}
private void dfs(int x) {
if (x >= boundary) {
ans.add(x);
return;
}
int last = x % 10;
if (last + k < 10) {
dfs(x * 10 + last + k);
}
if (k != 0 && last - k >= 0) {
dfs(x * 10 + last - k);
}
}
}复杂度
时间
O(2ⁿ)
第一位 9 种，之后每位最多两支，约 9·2ⁿ⁻¹ 个候选，每个拼接 O(n)
空间
O(n)
递归栈深度等于位数 n，不计输出数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 连续差相同的数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么用深搜，不直接枚举所有 n 位数再筛？+
n 最大到 9，n 位数有上亿个，逐个验证太慢。深搜每一位只展开两个候选，越界立刻剪枝，实际生成的候选大约是 9 乘 2 的 n 减 1 次方，远远小于全部 n 位数，省掉了海量无效枚举。
能不能改成广度优先？+
能。把层数当作位数，先把 1 到 9 入队，每次取出一个数，往后接末位加 k 和末位减 k 两个新数再入队，走到第 n 层的就是答案。和深搜等价，只是用队列换掉了递归栈。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 连续差相同的数字 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。