1291-顺次数.md

题目描述

顺次数

题目简述

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

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

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

分类

中等 枚举

思路

思路1

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
var sequentialDigits = function(low, high) {
  const lowLength = low.toString().length
  const highLength = high.toString().length
  const arr = []
  // 查找所有的长度为lowLength到highLength的所有顺次数
  for (let length = lowLength; length <= highLength; length++) {
    const num = Math.floor(123456789 / (10 ** (9 - length)))
    const oneoneone = Math.floor(111111111 / (10 ** (9 - length)))
    for (let i = 0; i < 10 - length; i++) {
      if (num + oneoneone * i > high) {
        break
      }
      if (num + oneoneone * i >= low) {
        arr.push(num + oneoneone * i)
      }
    }
  }
  return arr
  // 长度为n的话，有 9 - n个顺次数
};

• 问题分析
  • 问题的关键是如何构建出顺次数
    • 我的思路是构建长度为n的顺次数时，首先从123...n开始，加上n位全为1的数字，直到末位为9。例如1234, 1234 + 1111 = 2345，直到5678 + 1111 = 6789。
    • 如何确定第一位数字呢，123456789 / 10 ^ (9 - n)，同时对这个数做向下圆整即可。
    • 也很容易得出，长度为n的顺次数有9 - n个。
  • 如何查找符合要求的顺次数
    • 本题中的顺次数长度可以由最大最小值推断出来，在这个区间进行所有长度的顺次数构建。
    • 在构建所有顺次数的过程中，加上筛选条件即可，只有符合条件的才会被放入最终的结果。