-
Notifications
You must be signed in to change notification settings - Fork 0
/
numbersWithSameConsecutiveDifferences.py
68 lines (48 loc) · 1.51 KB
/
numbersWithSameConsecutiveDifferences.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# -*- coding: utf-8 -*-
"""
@author : zenithude
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
"""
from functools import reduce
class Solution:
def numsSameConsecDiff(self, N, K):
"""
:param N: int
:param K: int
:return: List[int]
"""
res = []
def dfs(cur):
if len(cur) == N:
if cur[0] == 0 and len(cur) > 1: return
res.append(reduce(lambda x, y: x * 10 + y, cur))
return
if K != 0:
if cur[-1] + K < 10:
dfs(cur + [cur[-1] + K])
if cur[-1] - K >= 0:
dfs(cur + [cur[-1] - K])
else:
dfs(cur + [cur[-1] + K])
for i in range(10):
dfs([i])
return res
obj = Solution()
print(obj.numsSameConsecDiff(2, 1))