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 题目讲解汇总(持续更新中...)