【Brute Force】967. Numbers With Same Consecutive Differences
【Brute Force】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]Note:
1 <= N <= 9
0 <= K <= 9解题思路：
让我们试着逐位写一些答案中的数字。 对于除第一位数字之外的每位数字，该数字最多有两个选项。以 9 位数字为例，这意味着最多只能有 9 * (2^8) 种可能。这小到足以使用暴力法来解决问题。
算法： 一个 N 位数字可以看作只是在一个 N-1 位数字后添加了最后一位数字。如果该 N-1 位数字是以数字 d 结尾，则 N 位数字将以 d-K 或 d+K 结束（前提是这些数字在 [0，9] 之间）。除了从一位数字初始化，算法只需要迭代 N - 1 次就能得到最后的答案。
我们将这些数字存储在 Set 结构中，以避免重复。
注意：只有 1 位数字能以 0 开头（数字 0）。
举例： 比如 N = 3，K = 4，我们在上一次迭代中可以得到数字 51，那么接下来需要构造的是 515 （51(-3) 最后一位小于 0 越界了，不考虑）；在上一次迭代中可以得到数字 26，那么接下来需要构造的是 262 （26(10) 最后一位大于 9 越界了，不考虑）。
注意：当 N =1 时， 无论 K 为多少，答案都是 [0,1,2,3,4,5,6,7,8,9]，尽管题目中没有提示，导致在编程的时候考虑太多了。
Python3 实现：
class Solution:
def numsSameConsecDiff(self, N, K):
"""
:type N: int
:type K: int
:rtype: List[int]
"""
ret = {i for i in range(1, 10)} # 初始化一个set
for _ in range(N - 1): # 迭代 N-1 次
ret2 = set()
for num in ret:
d = num % 10 # 取最后一位
if d - K >= 0:
ret2.add(10 * num + (d - K))
if d + K <= 9:
ret2.add(10 * num + (d + K))
ret = ret2
if N == 1: # 只有1位数字，还要包括0
ret.add(0)
return list(ret) # set转化为list
print(Solution().numsSameConsecDiff(3, 7)) # [929, 707, 292, 181]
print(Solution().numsSameConsecDiff(2, 0)) # [33, 66, 99, 11, 44, 77, 22, 55, 88]
print(Solution().numsSameConsecDiff(1, 1)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]腾讯云开发者
