网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 728. 自除数 ，难度为 简单。
Tag : 「模拟」、「打表」、「哈希表」、「二分」
自除数是指可以被它包含的每一位数整除的数。
- 例如，128128 是一个 自除数 ，因为
128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
自除数不允许包含 00 。
给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [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^41<=left<=right<=104
模拟
根据题意进行模拟即可。
代码：
class Solution { public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> ans = new ArrayList<>(); out:for (int i = left; i <= right; i++) { int cur = i; while (cur != 0) { int t = cur % 10; if (t == 0 || i % t != 0) continue out; cur /= 10; } ans.add(i); } return ans; } } 复制代码
class Solution: def selfDividingNumbers(self, left: int, right: int) -> List[int]: ans = [] for i in range(left, right + 1): cur, ok = i, True while cur and ok: ok = not ((t := cur % 10) == 0 or i % t != 0) cur //= 10 if ok: ans.append(i) return ans 复制代码
- 时间复杂度：令 n = right - left + 1n=right−left+1，复杂度为 O(n \log{right})O(nlogright)
- 空间复杂度：O(1)O(1)
打表 + 二分
利用数据范围只有 1e41e4，我们可以打表预处理出所有的自除数，通过二分找到 [left, right][left,right] 范围内的最小自除数，再从前往后找到所有合法的自除数。
代码：
class Solution { static List<Integer> list = new ArrayList<>(); static { out:for (int i = 1; i <= 10000; i++) { int cur = i; while (cur != 0) { int u = cur % 10; if (u == 0 || i % u != 0) continue out; cur /= 10; } list.add(i); } } public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> ans = new ArrayList<>(); int l = 0, r = list.size() - 1; while (l < r) { int mid = l + r >> 1; if (list.get(mid) >= left) r = mid; else l = mid + 1; } while (r < list.size() && list.get(r) <= right) ans.add(list.get(r++)); return ans; } } 复制代码
- 时间复杂度：令 n = right - left + 1n=right−left+1，复杂度为 O(\log{C} + n)O(logC+n)，其中 C = 1e4C=1e4
- 空间复杂度：O(C)O(C)
打表 + 哈希表
由于我们打表预处理的做法空间复杂度上界已经是 O(C)O(C)，所有我们可以干脆将索引也预处理出来，从而避免二分操作。
其中 hash[x]hash[x] 的含义为值不超过 xx 的最大自除数在 list 中的下标。
代码：
class Solution { static List<Integer> list = new ArrayList<>(); static int[] hash = new int[100010]; static { for (int i = 1; i <= 10000; i++) { int cur = i; boolean ok = true; while (cur != 0 && ok) { int u = cur % 10; if (u == 0 || i % u != 0) ok = false; cur /= 10; } if (ok) list.add(i); hash[i] = list.size() - 1; } } public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> ans = new ArrayList<>(); int idx = list.get(hash[left]) == left ? hash[left] : hash[left] + 1; while (idx < list.size() && list.get(idx) <= right) ans.add(list.get(idx++)); return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.726 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
