967. Numbers With Same Consecutive Differences 连续差相同的数字

@TOC

# 题目描述

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]
``````

Note:

1. 1 <= N <= 9
2. 0 <= K <= 9

# 解题方法

# DFS

python代码如下：

``````class Solution(object):
def numsSameConsecDiff(self, N, K):
"""
:type N: int
:type K: int
:rtype: List[int]
"""
if N == 1:
return [0, 1,2,3,4,5,6,7,8,9]
res = []
for i in range(1, 10):
self.dfs(res, i, N - 1, K)
return list(set(res))

def dfs(self, res, curint, N, K):
if N == 0:
res.append(curint)
return
last = curint % 10
if last + K <= 9:
self.dfs(res, curint * 10 + last + K, N - 1, K)
if last - K >= 0:
self.dfs(res, curint * 10 + last - K, N - 1, K)
``````

``````class Solution {
public:
vector<int> numsSameConsecDiff(int N, int K) {
if (N == 1)
return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int> res;
for (int i = 1; i <= 9; i++)
helper(res, i, N - 1, K);
return res;
}
void helper(vector<int>& res, int curint, int N, int K) {
if (N == 0) {
res.push_back(curint);
return;
}
int last = curint % 10;
if (last + K <= 9)
helper(res, curint * 10 + last + K, N - 1, K);
if (last - K >= 0 && K)
helper(res, curint * 10 + last - K, N - 1, K);
}
};
``````

# 日期

2018 年 12 月 30 日 —— 周赛差强人意