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

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

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) —

推荐阅读：
一段代码轻松解决wordpress定时发布失败的问题　 WordPress官网打不开 出现 429 Too Many Request 的原因　 下载更新wordpress程序及插件的方法　 禁用wordpress4.4+版本自动生成768w像素缩略图功能　 自动为wordpress文章图片添加alt属性和title属性　 如何为WordPress导航菜单、标签、出站等链接添加nofollow标签属性　 如何设置WordPress的RSS feed更新频率　 利用WordPress开发者调试模式解决PHP500内部服务器错误　 正确屏蔽 WordPress 版本号的代码　 WordPress插件WP First Letter Avatar代码版　
评论列表
添加评论