[LeetCode] 1291. Sequential Digits #1291

grandyang · 2019-05-30T16:34:13Z

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

这道题让返回给定区间范围内的整数，返回的整数需要各位上的数字是连续递增的，且返回的这些整数需要是有序的，题目中给的例子也能很好的表明题意。分析题目中的第一个例子，low 是 100，是个三位数，则返回的数至少也需要是个三位数，最小的就是 123，然后就是 234。题目中给定了区间范围，最大也不超过 10^9，就是说能返回的最大整数是 123456789，对于一个连续位的整数，只要比较一下是否在区间 [low, high] 内，就可以知道要不要返回。所以难点就变成了如何按顺序生成这些连续位的整数，一个比较好的方法就是从一位数开始生成，比如 1 -> 12 -> 123 -> 1234，可以发现其实就是每次加一位数，这个数字是就是原来个位数加1，但是有个限制条件，就是原来的个位数最多只能到8，这样才能再加新的一位。再者，由于起始位可以是任意的数字，所以可以把1到9都排入一个队列 queue，然后再开始 while 循环，每次取出队首元素，判断若在区间 [low, high] 内，则加入结果 res 中。否则判断若大于 high，则 break 掉循环，否则继续判断若个位上的数小于9，则在后面新加一位，这样所有满足要求的数字就存在结果 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 num = q.front(); q.pop();
            if (num >= low && num <= high) res.push_back(num);
            if (num > high) break;
            int d = num % 10;
            if (d < 9) q.push(num * 10 + d + 1);
        }
        return res;
    }
};

我们也可以不用 queue，而是每次都连续生成最高位固定的所有数字，用个 for 循环遍历1到9，这样数字的最高位就确定下来了，然后内部再用个 while 循环，循环条件是若当前数字 num 小于等于 high，并且最低位 next 小于 10。在 while 循环内部继续判断，若 num 大于等于 low，则将 num 加入结果 res，并且此时生成新的数字，通过将 num 乘以 10，并且加上自增1后的 next。这样生成数字的顺序不是有序的，最后需要整个将 res 排个序即可，参见代码如下：

解法二：

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++i) {
            int next = i, num = i;
            while (num <= high && next < 10) {
                if (num >= low) res.push_back(num);
                num = num * 10 + ++next;
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

再来看一种递归写法，整体思路和上面的一样，在 for 循环中调一个 dfs 子函数，在递归函数中，判断若 num 在范围 [low, high] 内，则将 num 加入结果 res。若 num 大于 high，或最低位 digit 大于等于9，则直接返回。否则调用递归函数，此时最低位 digit 自增1，num 变为 num * 10 + digit，参见代码如下：

解法三：

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        for (int i = 1; i <= 9; ++i) {
            dfs(low, high, i, 0, res);
        }
        sort(res.begin(), res.end());
        return res;
    }
    void dfs(int low, int high, int digit, int num, vector<int>& res) {
        if (num >= low && num <= high) res.push_back(num);
        if (num > high || digit > 9) return;
        dfs(low, high, digit + 1, num * 10 + digit, res);
    }
};

Github 同步地址:

#1291

参考资料：

https://leetcode.com/problems/sequential-digits/

https://leetcode.com/problems/sequential-digits/discuss/451862/C%2B%2B-BFS

https://leetcode.com/problems/sequential-digits/discuss/451849/JavaPython-3-Simple-codes.

https://leetcode.com/problems/sequential-digits/discuss/1711942/C%2B%2B-DFS-with-diagram-or-Basic-0-ms

LeetCode All in One 题目讲解汇总(持续更新中...)

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏