### 题目描述 自除数 是指可以被它包含的每一位数整除的数。 例如，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 <= 10^4 ### 题目解答 #### 思路 对于数字获取其每一位数，并且判断是否能整除，log10的复杂度，一共判断n个数字，将符合条件的添加到结果中。 **算法复杂度** 时间复杂度：对于某个数字的判断log10，最终的时间复杂度是$$O(nlog_{10}(n))$$ 空间复杂度：除了结果存储，时间复杂度是$$O(1)$$ #### 代码实现 ``` class Solution: def selfDividingNumbers(self, left: int, right: int) -> List[int]: res = list() for i in range(left, right+1): flag = True num = i while num > 0: div = num % 10 num = num // 10 # 自除数 不允许包含 0 或者不能整除 if div==0 or i % div != 0: flag = False break if flag: res.append(i) return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复