LeetCode 1291. 顺次数

作者:Choi Yang

更新于:7 个月前

字数统计:701 字

阅读时长:3 分钟

题目描述

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

提示：

10 <= low <= high <= 10^9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sequential-digits 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

也就是例如 1234这样的数字，然后给你一段区间确定范围。

官方给了枚举方式，反正数据量也不是很大，但是我觉得还是有很多数字没必要枚举，可以直接剪枝掉。我的做法是先求出最小值和最大值对应字符串的长度，即求出我们能枚举的数字的长度范围。

然后我们的起点的最小值从 1 开始，起点的最大值从 10-len 开始。为什么是 10-len？举例说明，示例 1 给的是 [100,300]范围的值，那么可枚举的长度 len 为 3，起点的最大值就位 10 - 3 = 7。那么此时顺次数为 789 但是不在我们区间范围内，舍弃。然后8、9开头的数字就不需要枚举了。 这样，我们就能剪掉一部门数据了。（虽然暴力是永远滴神...）

javascript

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
var sequentialDigits = function (low, high) {
  let res = [];
  let lowLen = low.toString().length;
  let highLen = high.toString().length;
  for (let i = lowLen; i <= highLen; i++) {
    for (let j = 1; j <= 10 - i; j++) {
      let str = "";
      let num = j;
      str += num;
      let k = i - 1;
      while (k--) {
        num++;
        str += num;
      }
      let ans = parseInt(str);
      if (ans >= low && ans <= high) {
        res.push(ans);
      }
    }
  }
  return res;
};

cpp

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> res;
        int lowLen = to_string(low).size();
        int highLen = to_string(high).size();
        for(int i=lowLen;i<=highLen;i++){
            for(int j=1;j<=10-i;j++){
                string str = "";
                int num = j;
                str += to_string(num);
                int k = i-1;
                while(k--){
                    num++;
                    str += to_string(num);
                }
                int ans = stoi(str);
                if(ans>=low && ans<=high){
                    res.push_back(ans);
                }
            }
        }
        return res;
    }
};

java

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> res = new ArrayList<>();
        int lowLen = String.valueOf(low).length();
        int highLen = String.valueOf(high).length();
        for(int i=lowLen;i<=highLen;i++){
            for(int j=1;j<=10-i;j++){
                String str = "";
                int num = j;
                str += num;
                int k = i-1;
                while(k-->0){
                    num++;
                    str += num;
                }
                int ans = Integer.parseInt(str);
                if(ans>=low && ans<=high){
                    res.add(ans);
                }
            }
        }
        return res;
    }
}

python

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        lowLen = len(str(low))
        highLen = len(str(high))
        for i in range(lowLen,highLen+1):
            for j in range(1,10-i+1):
                num = j
                str = ""
                str += str(num)
                k = i-1
                while k>0:
                    num += 1
                    str += str(num)
                    k -= 1
                ans = int(str)
                if ans>=low and ans<=high:
                    res.append(ans)
        return res

学如逆水行舟，不进则退

Contributors

Choi Yang