# 967. Numbers With Same Consecutive Differences

Return all non-negative integers of length `n` such that the absolute difference between every two consecutive digits is `k`.

Note that every number in the answer must not have leading zeros except for the number `0` itself. For example, `01` has one leading zero and is invalid, but `0` is valid.

You may return the answer in any order.

Example 1:

``````Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
``````

Example 2:

``````Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
``````

Example 3:

``````Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]
``````

Example 4:

``````Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
``````

Example 5:

``````Input: n = 2, k = 2
Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]
``````

Constraints:

• `2 <= n <= 9`
• `0 <= k <= 9`

``````class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
vector<int> res{1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 1; i < n; ++i) {
vector<int> cur;
for (int num : res) {
int digit = num % 10;
if (digit + k <= 9) cur.push_back(num * 10 + digit + k);
if (k != 0 && digit - k >= 0) cur.push_back(num * 10 + digit - k);
}
res = cur;
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
vector<int> res;
for (int i = 1; i <= 9; ++i) {
helper(i, n - 1, k, res);
}
return res;
}
void helper(int num, int n, int k, vector<int>& res) {
if (n == 0) {
res.push_back(num);
return;
}
int digit = num % 10;
if (digit + k <= 9) helper(num * 10 + digit + k, n - 1, k, res);
if (k != 0 && digit - k >= 0) helper(num * 10 + digit - k, n - 1, k, res);

}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/967

https://leetcode.com/problems/numbers-with-same-consecutive-differences/

https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211193/C%2B%2B-DFS

https://leetcode.com/problems/numbers-with-same-consecutive-differences/discuss/211183/JavaC%2B%2BPython-Iterative-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation