DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff
- 时间:2020-09-07 12:13:31
- 分类:网络文摘
- 阅读:73 次
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
For both DFS and BFS Algorithms (See below), the special cases have to be handled properly. For example, when N=1 one digit, the answer is the array containing single digits from 0 to 9. And when K is 0, the answer is an array of 9 solutions each containing duplicate digits: [111.., 222…, 333…] and so on.
The Bruteforce may not work practically as when N is 9, the search range is O(10^N) which could take a while.
Find Numbers With Same Consecutive Differences by Depth First Search Algorithm
For DFS, we start by putting the first digit (left-most) please note that we don’t try 0 as it is invalid. When we reach the N digits, we push the result.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution: def numsSameConsecDiff(self, N: int, K: int) -> List[int]: if N == 1: return list(range(10)) if K == 0: return [str(x)*N for x in range(1, 10)] res = [] for i in range(1, 10): self.dfs(N, K, i, res) return res def dfs(self, N, K, i: int, res: List[int]) -> List[int]: if N == 1: res.append(i) return c = i % 10 if c + K < 10: self.dfs(N - 1, K, i * 10 + (c + K), res) if c - K >= 0: self.dfs(N - 1, K, i * 10 + (c - K), res) |
class Solution: def numsSameConsecDiff(self, N: int, K: int) -> List[int]: if N == 1: return list(range(10)) if K == 0: return [str(x)*N for x in range(1, 10)] res = [] for i in range(1, 10): self.dfs(N, K, i, res) return res def dfs(self, N, K, i: int, res: List[int]) -> List[int]: if N == 1: res.append(i) return c = i % 10 if c + K < 10: self.dfs(N - 1, K, i * 10 + (c + K), res) if c - K >= 0: self.dfs(N - 1, K, i * 10 + (c - K), res)
When we recursively try next digit, we only need to check current digit plus or minus K forms a valid next number. The complexity is O(N*2^N). For space complexity, the usage of Recursion implies O(N), and we use array to store the final answer which could be up to O(9*2^(N-1)). Therefore, the space complexity is O(2^N).
Breadth First Search Algorithm to Find Numbers With Same Consecutive Differences
BFS Algorithm expands the search tree level by level. For example, we finish numbers of 1 digit, and then search all 2-digit numebrs etc.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution: def numsSameConsecDiff(self, N: int, K: int) -> List[int]: if N == 1: return list(range(10)) if K == 0: return [str(x)*N for x in range(1, 10)] res = [] Q = list(range(1, 10)) while len(Q) > 0: cur = str(Q.pop(0)) if len(cur) == N: res.append(cur) else: x = int(cur[-1]) if x + K < 10: Q.append(cur + str(x + K)) if x - K >= 0: Q.append(cur + str(x - K)) return res |
class Solution: def numsSameConsecDiff(self, N: int, K: int) -> List[int]: if N == 1: return list(range(10)) if K == 0: return [str(x)*N for x in range(1, 10)] res = [] Q = list(range(1, 10)) while len(Q) > 0: cur = str(Q.pop(0)) if len(cur) == N: res.append(cur) else: x = int(cur[-1]) if x + K < 10: Q.append(cur + str(x + K)) if x - K >= 0: Q.append(cur + str(x - K)) return res
We use a queue to keep the numbers and we expand the next digits into the queue. The BFS solution has similar time and space complexity.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:What is the largest prime factor of the number 600851475143 ? Can we Construct K Palindrome Strings? Sum of Even Fibonacci Numbers Sum of Multiples of 3 and 5 How to Design Underground System using Several Hash Maps? How to Remove Zero Sum Consecutive Nodes from Linked List using Depth First Search and Breadth First Search Algorithm to Open th Dynamic Programming (Memoization) to Sort Integers by The Power Applicable Accounting Software For Churches How to Balance a Binary Search Tree using Recursive Inorder Trav
- 评论列表
-
- 添加评论