[LeetCode] 1291. Sequential Digits 顺次数

2022/4/4 23:49:04

本文主要是介绍[LeetCode] 1291. Sequential Digits 顺次数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!


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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中...)



这篇关于[LeetCode] 1291. Sequential Digits 顺次数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程