LeetCode 题解工作台
自除数
自除数 是指可以被它包含的每一位数整除的数。 例如， 128 是一个 自除数 ，因为 128 % 1 == 0 ， 128 % 2 == 0 ， 128 % 8 == 0 。 自除数 不允许包含 0 。 给定两个整数 left 和 right ，返回一个列表， 列表的元素是范围 [left, rig…
1
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数学·driven
答案摘要
我们定义一个函数 ，用来判断 是否是自除数。函数的实现思路如下： 我们用 来记录 的值，然后不断地对 除以 ，直到 为 。在这个过程中，我们判断 的末位是否为 ，或者 是否不能被 的末位整除，如果满足这两个条件中的任意一个，那么 就不是自除数，返回 。否则遍历完所有的位数后，返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
自除数 是指可以被它包含的每一位数整除的数。
- 例如，
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
解题思路
方法一：模拟
我们定义一个函数 ，用来判断 是否是自除数。函数的实现思路如下：
我们用 来记录 的值，然后不断地对 除以 ，直到 为 。在这个过程中，我们判断 的末位是否为 ，或者 是否不能被 的末位整除，如果满足这两个条件中的任意一个，那么 就不是自除数，返回 。否则遍历完所有的位数后，返回 。
最后，我们遍历区间 中的所有数，对每个数调用 ，如果返回 ，那么我们就将这个数加入答案数组中。
时间复杂度 ，其中 是区间 中的元素个数，而 ，表示区间中的最大值。
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
def check(x: int) -> bool:
y = x
while y:
if y % 10 == 0 or x % (y % 10):
return False
y //= 10
return True
return [x for x in range(left, right + 1) if check(x)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | We iterate through each digit in the given number; therefore, the time complexity is |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Focus on how efficiently the candidate can iterate through a range and check divisibility.
- question_mark
Look for an understanding of string manipulation or array handling to extract digits from numbers.
- question_mark
Evaluate how the candidate handles edge cases such as numbers with zeros or single-digit numbers.
常见陷阱
外企场景- error
Forgetting to check for the digit zero in the number, which would lead to incorrect results.
- error
Inefficient implementation, causing slower performance for larger ranges.
- error
Not handling numbers that have a single digit or edge cases like 10, 100, etc.
进阶变体
外企场景- arrow_right_alt
Consider a variant where the range can be negative, requiring handling of negative numbers.
- arrow_right_alt
Expand the problem to allow for ranges with floating-point numbers and non-integer divisibility.
- arrow_right_alt
Solve the problem without converting numbers to strings, relying purely on mathematical operations to extract digits.