엔지니어 게시판
LeetCode 솔루션 분류

[9/3] 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. 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.
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
                
전체 404 / 9 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0