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 
评论列表
添加评论