TNotes.leetcode

Appearance

0728. 自除数【简单】

0728. 自除数【简单】 ​

1. 📝 题目描述 ​

  • 自除数 是指可以被它包含的每一位数整除的数。
  • 例如，128 是一个 自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
  • 自除数 不允许包含 0。
  • 给定两个整数 left 和 right，返回一个列表，列表的元素是范围 [left, right]（包括两个端点）内所有的 自除数。

示例 1：

txt
输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

示例 2：

txt
输入：left = 47, right = 85
输出：[48,55,66,77]

提示：

  • 1 <= left <= right <= 10^4

2. 🫧 评价 ​

  • s.1、s.2 两种解法非常类似，都是逐位检查是否可以被整除。

3. 🎯 s.1 - 暴力枚举法 ​

js
/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
var selfDividingNumbers = function (left, right) {
  const result = []

  // 检查一个数是否为自除数
  const isSelfDividing = (num) => {
    let temp = num
    while (temp > 0) {
      const digit = temp % 10
      // 如果包含0或者不能被某一位整除，则不是自除数
      if (digit === 0 || num % digit !== 0) {
        return false
      }
      temp = Math.floor(temp / 10)
    }
    return true
  }

  // 遍历范围内的每个数字
  for (let i = left; i <= right; i++) {
    if (isSelfDividing(i)) {
      result.push(i)
    }
  }

  return result
}
  • 时间复杂度：O(n⋅log⁡m)，其中 n 是范围大小 (right−left+1)，m 是范围内的数字，log⁡m 是数字的位数
  • 空间复杂度：O(1)，不考虑结果数组的话，只使用了常数个额外变量

4. 🎯 s.2 - 字符串处理 ​

js
/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
var selfDividingNumbers = function (left, right) {
  const result = []

  const isSelfDividing = (num) => {
    const digits = num.toString()
    for (const digit of digits) {
      const d = parseInt(digit)
      // 如果包含0或者不能被某一位整除，则不是自除数
      if (d === 0 || num % d !== 0) {
        return false
      }
    }
    return true
  }

  for (let i = left; i <= right; i++) {
    if (isSelfDividing(i)) {
      result.push(i)
    }
  }

  return result
}
  • 时间复杂度：O(n⋅log⁡m)，其中 n 是范围大小，log⁡m 是数字的位数
  • 空间复杂度：O(log⁡m)，需要额外空间存储数字的字符串表示

Discussions