leetcode 728. 自除数

leetcode 728. 自除数

题目描述

728. 自除数

自除数 是指可以被它包含的每一位数整除的数。

例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。 自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。

示例 1：

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

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

提示：

1 <= left <= right <= 104

解题思路

法1

1. 我们遍历范围 [left, right] 内的所有数字。

对于每个数字 num，我们调用 isSelfDividing 函数来检查它是否是自除数。如果是自除数，则将其添加到结果列表 result 中。

2. 设计一个函数用于检查一个数字是否是自除数。

我们使用变量 n 来迭代数字 num 的每一位。对于每个位数，我们通过 n % 10 取出当前位的数字。如果当前位是 0 或者 num 不能被当前位整除，则返回 false，表示该数字不是自除数。然后，我们将 n 除以 10，以便处理下一位数。如果遍历完所有位数后都没有返回 false，则说明该数字是自除数，返回 true。

• 时间复杂度(O(nlogn)
• 空间复杂度(O(n))

执行结果

法1

func selfDividingNumbers(left int, right int) []int {
 result := []int{}

 for num := left; num <= right; num++ {
  if isSelfDividing(num) {
   result = append(result, num)
  }
 }

 return result
}

func isSelfDividing(num int) bool {
 n := num

 for n > 0 {
  digit := n % 10
  if digit == 0 || num%digit != 0 {
   return false
  }
  n /= 10
 }

 return true
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.9 MB , 在所有 Go 提交中击败了 73.68% 的用户 通过测试用例： 31 / 31 炫耀一下:

法2

法3