LeetCode 솔루션 분류
[9/3] 967. Numbers With Same Consecutive Differences
본문
Medium
2133169Add to ListShareReturn 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. For example, 01
has one leading zero and is invalid.
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]
Constraints:
2 <= n <= 9
0 <= k <= 9
Accepted
91,777
Submissions
166,904
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 44 ms, faster than 91.16% of Python3 online submissions for Numbers With Same Consecutive Differences.
Memory Usage: 14.1 MB, less than 73.81% of Python3 online submissions for Numbers With Same Consecutive Differences.
Memory Usage: 14.1 MB, less than 73.81% of Python3 online submissions for Numbers With Same Consecutive Differences.
from collections import deque
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
# bfs solution - beats 91%
queue = collections.deque([ (1, i) for i in range(1,10) ])
res = []
while queue:
length, num = queue.popleft()
if length == n: res.append(num)
else:
for i in range(10):
if abs(num%10 - i) == k:
queue.append((length + 1, num*10+i))
return res
# dfs solution - accepted beats 40 %
LEN = n
K = k
res = []
def dfs(num):
if len(num) == LEN:
res.append(int("".join(num)))
return
# first digit
if not len(num):
for i in range(1, 10):
num.append(str(i))
dfs(num)
num.pop()
# second digit ~ nth digit
else:
last_digit = int(num[-1])
if last_digit + K < 10:
num.append(str(last_digit + K))
dfs(num)
num.pop()
if K and 0<=last_digit - K <10:
num.append(str(last_digit-K))
dfs(num)
num.pop()
dfs([])
return res