LeetCode 솔루션

[9/3] 967. Numbers With Same Consecutive Differences

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.09.03 10:31

2,880 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

967. Numbers With Same Consecutive Differences

Medium

2133169Add to ListShare

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

#Microsoft, #Uber

링크

https://leetcode.com/problems/numbers-with-same-consecutive-differences/ 983 회 연결

익명
작성일 2022.09.03 11:02

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

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.
[code=Python 3]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
                
[/code]