经典算法实例应用：自除数-尧图网络科技

我们先来看题目描述：

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

例如，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

解决方案

方法一：直接判断

遍历范围[left,right] 内的所有整数，分别判断每个整数是否为自除数。

根据自除数的定义，如果一个整数不包含 0 且能被它包含的每一位数整除，则该整数是自除数。判断一个整数是否为自除数的方法是遍历整数的每一位，判断每一位数是否为 0 以及是否可以整除该整数。

遍历整数的每一位的方法是，每次将当前整数对 10 取模即可得到当前整数的最后一位，然后将整数除以 10。重复该操作，直到当前整数变成 0 时即遍历了整数的每一位。

代码

Python3

class Solution: def selfDividingNumbers(self, left: int, right: int) -> List[int]: def isSelfDividing(num: int) -> bool: x = num while x: x, d = divmod(x, 10) if d == 0 or num % d: return False return True return [i for i in range(left, right + 1) if isSelfDividing(i)]

Java

class Solution { public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> ans = new ArrayList<Integer>(); for (int i = left; i <= right; i++) { if (isSelfDividing(i)) { ans.add(i); } } return ans; } public boolean isSelfDividing(int num) { int temp = num; while (temp > 0) { int digit = temp % 10; if (digit == 0 || num % digit != 0) { return false; } temp /= 10; } return true; } }

public class Solution { public IList<int> SelfDividingNumbers(int left, int right) { IList<int> ans = new List<int>(); for (int i = left; i <= right; i++) { if (IsSelfDividing(i)) { ans.Add(i); } } return ans; } public bool IsSelfDividing(int num) { int temp = num; while (temp > 0) { int digit = temp % 10; if (digit == 0 || num % digit != 0) { return false; } temp /= 10; } return true; } }

C++

class Solution { public: bool isSelfDividing(int num) { int temp = num; while (temp > 0) { int digit = temp % 10; if (digit == 0 || num % digit != 0) { return false; } temp /= 10; } return true; } vector<int> selfDividingNumbers(int left, int right) { vector<int> ans; for (int i = left; i <= right; i++) { if (isSelfDividing(i)) { ans.emplace_back(i); } } return ans; } };

复杂度分析

时间复杂度：O(n log right) ，其中 n 是范围内的整数个数，right 是范围内的最大整数。对于范围内的每个整数，需要 O(log right) 的时间判断是否为自除数。

空间复杂度：O(1) 。除了返回值以外，使用的额外空间为 O(1) 。