LeetCode 728. 自除数
题目描述
✅ 728. 自除数
题意分析
枚举指定闭区间内的自除数：各十进制数位都非零，并且原数能够被每个数位整除。
解法：枚举 + 按位检查
核心思路
[!blue]
区间最多到
10^4，可以逐个枚举候选，再检查它的每个十进制数位。保留原数num，用副本x拆位：x % 10取出当前个位d，x / 10去掉已经检查的个位，因此每个数位恰好检查一次。每位必须同时满足
d != 0和num % d == 0。整除判断始终针对完整原数，不能改用逐渐缩短的x；任一数位失败，这个候选就不可能是自除数，可以立即返回false。代码先判断d == 0，利用短路避免对 0 取模。题目中的候选均为正数，反复除以 10 后
x一定变成 0，表示所有数位都已通过。外层按闭区间从小到大枚举，通过的数直接加入结果，既不会遗漏端点，也自然保持升序。
解题步骤
- 从 left 到 right 逐个枚举整数。
- 使用临时变量拆分当前整数的数位。
- 遇到零或不能整除原数的数位，立即判定失败。
- 所有数位通过则按枚举顺序加入答案。
代码实现
class Solution {
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> answer = new ArrayList<>();
for (int x = left; x <= right; x++) {
if (ok728(x)) {
answer.add(x);
}
}
return answer;
}
private boolean ok728(int num) {
// 保留原数用于整除检查，副本只负责逐位拆分。
int x = num;
while (x > 0) {
int d = x % 10;
// 先排除零，再对该数位取模，避免除零。
if (d == 0 || num % d != 0) {
return false;
}
x /= 10;
}
return true;
}
}
func selfDividingNumbers(left int, right int) []int {
answer := make([]int, 0)
for x := left; x <= right; x++ {
if ok728(x) {
answer = append(answer, x)
}
}
return answer
}
func ok728(num int) bool {
// 保留原数用于整除检查，副本只负责逐位拆分。
x := num
for x > 0 {
d := x % 10
// 先排除零，再对该数位取模，避免除零。
if d == 0 || num%d != 0 {
return false
}
x /= 10
}
return true
}
复杂度分析
- 时间复杂度：设区间内整数个数为
R = right-left+1，每个数最多有D位，时间为 $O(RD)$，其中 $D=\lfloor\log_{10}right\rfloor+1$。- 空间复杂度：除输出外为 $O(1)$，只保存原数、副本和当前数位。
关键点总结
[!green]
- 原数负责整除检查，副本负责拆位。
- 零必须在取模运算之前排除。
- 升序枚举自然得到升序结果。
易错点总结
[!yellow]
- 判断临时副本能否被当前位整除：检查对象发生了变化。
- 先计算对零取模再判断数位零：会发生非法运算。
- 右端点使用严格小于：遗漏闭区间最后一个数。
- 修改外层枚举变量来拆位：破坏后续枚举进度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2520. 统计能整除数字的位数 | 简单 | 两题都检查十进制数位是否整除原数，原题计合格数位，本题要求每一位都非零且都合格。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！