Compute the Sequential Digits within a Range using DFS, BFS, or

  • 时间：2020-09-13 14:33:25
  • 分类：网络文摘
  • 阅读：130 次

An integer has sequential digits if and only if each digit in the number is one more than the previous digit. Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:
Input: low = 100, high = 300
Output: [123,234]

Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:
10 <= low <= high <= 10^9

Hints:
Generate all numbers with sequential digits and check if they are in the given range.
Fix the starting digit then do a recursion that tries to append all valid digits.

The very brutal solution would be to check each number between [low, high] and test if it qualifies the sequential digits. This will run in O(N) where N is the count of all numbers within in the range. Given the range may be large, this solution is not practical.

A Better Bruteforce Algorithm

A better bruteforce solution will be to list all sequential digits within the range – which is 32-bit signed integers. Searching from the two digits, then third digits so on until the value in the candidate list is larger than the upperbound of the range. The bruteforce complexity is O(1) – so as the space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        all = [12,23,34,45,56,67,78,89,\
                         123,234,345,456,567,678,789,\
                         1234,2345,3456,4567,5678,6789,\
                         12345,23456,34567,45678,56789,\
                         123456,234567,345678,456789,\
                         1234567,2345678,3456789,\
                         12345678,23456789,\
                         123456789]
        res = []
        for i in all:
            if i >= low and i <= high:
                res.append(i)
            if i >= high:
                break
        return res
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        all = [12,23,34,45,56,67,78,89,\
                         123,234,345,456,567,678,789,\
                         1234,2345,3456,4567,5678,6789,\
                         12345,23456,34567,45678,56789,\
                         123456,234567,345678,456789,\
                         1234567,2345678,3456789,\
                         12345678,23456789,\
                         123456789]
        res = []
        for i in all:
            if i >= low and i <= high:
                res.append(i)
            if i >= high:
                break
        return res

Translating to C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> all = {12,23,34,45,56,67,78,89,
                         123,234,345,456,567,678,789,
                         1234,2345,3456,4567,5678,6789,
                         12345,23456,34567,45678,56789,
                         123456,234567,345678,456789,
                         1234567,2345678,3456789,
                         12345678,23456789,
                         123456789};
        vector<int> result;
        for (const auto &n: all) {
            if (n >= low && n <= high) {
                result.push_back(n);
            }
            if (n >= high) break;
        }
        return result;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> all = {12,23,34,45,56,67,78,89,
                         123,234,345,456,567,678,789,
                         1234,2345,3456,4567,5678,6789,
                         12345,23456,34567,45678,56789,
                         123456,234567,345678,456789,
                         1234567,2345678,3456789,
                         12345678,23456789,
                         123456789};
        vector<int> result;
        for (const auto &n: all) {
            if (n >= low && n <= high) {
                result.push_back(n);
            }
            if (n >= high) break;
        }
        return result;
    }
};

Another bruteforce algorithm to generate the sequential digits between the range is to iterate 10 times and start with each possible digit from 1 to 9:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> result;
        for(int i = 1; i < 10; ++ i) {
            int value = 0;
            for(int j = i; j < 10; ++ j) {
                value = value * 10 + j;
                if ((value <= high) && (value >= low)) {
                    result.push_back(value);
                }
            }
        }
        sort(begin(result), end(result));
        return result;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> result;
        for(int i = 1; i < 10; ++ i) {
            int value = 0;
            for(int j = i; j < 10; ++ j) {
                value = value * 10 + j;
                if ((value <= high) && (value >= low)) {
                    result.push_back(value);
                }
            }
        }
        sort(begin(result), end(result));
        return result;
    }
};

This requires sorting the result set. The Python implementation:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        for i in range(1, 10):
            value = 0
            for j in range(i, 10):
                value = value * 10 + j
                if value >= low and value <= high:
                    ans.append(value)
        return sorted(ans)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        for i in range(1, 10):
            value = 0
            for j in range(i, 10):
                value = value * 10 + j
                if value >= low and value <= high:
                    ans.append(value)
        return sorted(ans)

Depth First Search Algorithm

Now, comes to the classic search solution – Depth First Search (DFS). We can start searching at 1 to 9, then each time append a increasing digit if the last digit is not 9. The implementation of DFS is usually based on recursion, which requires maintaining stack calls during runtime – which will be handled by the compiler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        def dfs(x):
            if x >= low and x <= high:
                ans.append(x)
            if x > high:
                return
            y = x % 10
            if y != 9:
                dfs(x * 10 + (y + 1))
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        def dfs(x):
            if x >= low and x <= high:
                ans.append(x)
            if x > high:
                return
            y = x % 10
            if y != 9:
                dfs(x * 10 + (y + 1))
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)

Same DFS algorithm implemented in C++ may look a bit verbose – given the use of vector – appending the result from DFS function to the result vector using the insert method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++ i) {
            vector<int> v = dfs(low, high, i);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        sort(begin(res), end(res));
        return res;
    }
    
private:
    vector<int> dfs(int low, int high, int cur = 0) {
        vector<int> res;
        if (cur >= low && cur <= high) {
            res.push_back(cur);
        }
        if (cur >= high) {
            return res;
        }
        int x = cur % 10;
        if (x != 9) {
            vector<int> v = dfs(low, high, cur * 10 + x + 1);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        return res;
    }    
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++ i) {
            vector<int> v = dfs(low, high, i);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        sort(begin(res), end(res));
        return res;
    }
    
private:
    vector<int> dfs(int low, int high, int cur = 0) {
        vector<int> res;
        if (cur >= low && cur <= high) {
            res.push_back(cur);
        }
        if (cur >= high) {
            return res;
        }
        int x = cur % 10;
        if (x != 9) {
            vector<int> v = dfs(low, high, cur * 10 + x + 1);
            if (!v.empty()) {
                res.insert(res.end(), begin(v), end(v));
            }
        }
        return res;
    }    
};

Breadth First Search Algorithm

The BFS (Breadth First Search) Algorithm avoids the recursion stacks – by using a queue. The next sequential digits (child nodes) are pushed to the queue after a current number is dequed until the queue becomes empty – which means all solutions have been tried.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        Q = []
        for i in range(1, 10):
            Q.append(i)
        res = []
        while len(Q) > 0:
            p = Q.pop(0)
            if p >= low and p <= high:
                res.append(p)
            x = p % 10            
            if x != 9 and x < high:
                Q.append(p * 10 + x + 1)
        return sorted(res)
class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        Q = []
        for i in range(1, 10):
            Q.append(i)
        res = []
        while len(Q) > 0:
            p = Q.pop(0)
            if p >= low and p <= high:
                res.append(p)
            x = p % 10            
            if x != 9 and x < high:
                Q.append(p * 10 + x + 1)
        return sorted(res)

Translating to C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            int p = Q.front();
            Q.pop();
            if (p >= low && p <= high) {
                res.push_back(p);
            }
            if (p < high) {
                int x = p % 10;
                if (x != 9) {
                    Q.push(p * 10 + x + 1);
                }
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        queue<int> Q;
        for (int i = 1; i <= 9; ++ i) {
            Q.push(i);
        }
        while (!Q.empty()) {
            int p = Q.front();
            Q.pop();
            if (p >= low && p <= high) {
                res.push_back(p);
            }
            if (p < high) {
                int x = p % 10;
                if (x != 9) {
                    Q.push(p * 10 + x + 1);
                }
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};

All these implementations are O(1) in time given the range is restricted to a 32-bit signed integer – thus it takes at most 10 iterations to search the solution space.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
浙江卫视直播-浙江卫视在线直播观看「高清」　 河南卫视在线直播-河南卫视直播在线观看「高清」　 北京卫视直播-北京卫视在线直播观看「高清」　 天津卫视直播-天津卫视在线直播观看「高清」　 安徽卫视直播-安徽卫视在线直播观看「高清」　 湖北卫视直播-湖北卫视在线直播观看「高清」　 河北卫视直播-河北卫视在线直播观看「高清」　 山西卫视直播-山西卫视在线直播观看「高清」　 山东卫视直播-山东卫视在线直播观看「高清」　 辽宁卫视直播-辽宁卫视在线直播观看「高清」　
评论列表
添加评论