sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

顺次数-1291 #116

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

我们定义「顺次数」为:每一位上的数字都比前一位上的数字大 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

先通过 lowhigh之间的长度对比,得到总共有几种数字长度。

然后循环这些数字长度 len 作为目标, 1 作为最小起点, 10 - len 作为最大的起点,不断尝试构造出长度为 len 的顺位数字即可。

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
let sequentialDigits = function (low, high) {
  let lowLen = low.toString().length
  let highLen = high.toString().length
  let lens = []
  for (let i = lowLen; i <= highLen; i++) {
    lens.push(i)
  }

  let res = []
  for (let i = 0; i < lens.length; i++) {
    let len = lens[i]
    for (let start = 1; start <= 10 - len; start++) {
      let num = start

      for (let n = start + 1; n < start + len; n++) {
        num = 10 * num + n
      }
      if (num <= high && num >= low) {
        res.push(num)
      }
    }
  }

  return res
}
zhangfei18 commented 4 years ago

请问递归和回溯体现在了哪里呢

Gjb7598189 commented 4 years ago

function f(low, high) { let l1 = low.toString().length, l2 = high.toString().length, res = [];

const lenArr = [];
for (let i = l1; i <= l2; i ++) { lenArr.push(i) };
console.log(lenArr)
for (let i = 0; i < lenArr.length; i ++) {
    const len = lenArr[i], min = 1; max = 10 - len;
    for (let j = min; j <= max; j ++) {
        var str = '', start = j;
        for (let k = 1; k <= len; k ++) {
              str += start;
                start++;

        }
        const num = Number(str);
        if (num >= low && num <= high) res.push(num)
    }
}

return res;

}

Chocolate1999 commented 4 years ago
/**
 * @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    
};
daomingQian commented 3 years ago

var sequentialDigits = function(low, high) { let arr = [ 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 ] let res = []; for(let num of arr){ if(num>=low && num<=high){ res.push(num); } }

return res;

};

55utah commented 3 years ago
function sequentialDigits(low: number, high: number): number[] {
    /**  对123456789字符串滑动窗口处理  */
    const sam = '123456789'
    const result = []
    const max = high.toString().length
    for (let i = low.toString().length; i <= max; i++) {
        for (let k = 0; k <= 9 - i; k++) {
            const v = Number(sam.slice(k, k + i))
            if (v >= low && v <= high) result.push(v)
            else if (v > high) break
        }
    }
    return result
}
SuAgnes commented 2 years ago
  var sequentialDigits = function (low, high) {
        let init = '123456789',
            len = low.toString().length,
            initI = low.toString().slice(0, 1);
            i = init.substr(initI - 1, len) >= low ? initI - 1 : initI;
            num = 0;
            res = [];
        while (num < high && len < 9) {
            if (9 - i < len) {
                len += 1;
                i = 0;
            }
            num = init.substr(i, len);
            if (num <= high) {
                res.push(num);
            }
            i++;
        }
        return res;
    };
pandaxue commented 1 year ago
 var lowLen = low.toString().length
 var highLen = high.toString().length    
var str = "123456789"
    var seq = [];
    while(lowLen<= highLen){
        var idx = 0
        while(lowLen + idx <= str.length) {
            var num = parseInt(str.substring(idx, idx+ lowLen))
            if(num>=low && num <= high){
                console.log(num)
                seq.push(num)
            }
            idx++
        }
        lowLen++
    }
    return seq