LeetCode 728. 自除数

2021-03-24 HGNULB 约 11 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 728. 自除数

题意分析

给定闭区间 [left, right]，要求返回区间内所有「自除数」组成的列表。一个数是自除数，当且仅当它能被自己的每一位数字整除。题目额外强调：自除数不允许包含数字 0，因为除以 0 无意义。

定义里有一个必须咬死的细节：整除的被除数始终是原始的数，而不是逐位剥离过程中剩下的部分。判断 128 时，要问的是「128 能否被 1、2、8 整除」，而不是「12 能否被 2 整除」。这一句读得快就会写错，且错法很隐蔽——很多数在两种解释下结果相同，只有少数用例能暴露差异。

关于 0 的处理也有两层。含 0 的数直接不合格，这是题目明说的；但更实际的意义是它保护了取模运算不崩溃。实现时这两件事可以合并成同一个判断，而且必须在做除法之前判断，顺序反了就是运行时异常。

约束是 $1 \le left \le right \le 10^4$。区间最多一万个数，每个数最多五位。这个规模小到几乎不构成限制，说明题目并不想考任何数论优化，而是考你能否把一个「对每个元素做独立判定」的任务拆干净：外层负责遍历与收集，内层负责单个数的判定。别去想什么打表或者筛法，那是对着约束过度设计。

边界方面：left 最小为 1，而个位数 1 到 9 全都是自除数（d 就是它自己，必然整除），所以答案不会出现空列表以外的意外；只有当区间完全落在没有自除数的段落里（比如 [80, 87]）时才返回空列表，此时 Java 的 ArrayList 与 Go 的空切片都要保证是「空但非 null」。

解法：枚举 + 按位检查

核心思路

这道题不存在「暴力→优化」的落差，因为暴力本身就是最优解，值得推敲的是如何把判定逻辑组织得不出错。真正的思路重点在于把两件事彻底分离：外层枚举区间内的每个候选，内层用一个纯函数判定单个候选是否合格。一旦混在一起写，就很容易在剥位的循环里误用了被改动过的变量。

内层判定的不变量要写清楚：设待判定的原始数为 num，用一个工作副本 x 承载剥位过程。循环中始终保持 x 是 num 去掉若干低位后剩下的部分，而 num 从头到尾不被修改。每一轮取出 d = x % 10 作为当前考察的一位，然后用 num % d 而不是 x % d 来检验整除性。副本 x 只承担「还有哪些位没检查」的职责，被除数的角色永远由 num 独占。这个「原值与工作副本分离」的约定，就是本题唯一的技术点。

剥位循环的终止条件是 x > 0。为什么是大于 0 而不是大于等于：当 x 变成 0 时说明所有位都已取出，再进一层就会取到一个不存在的高位 0，反而把合格的数误判掉。而由于题目保证 num ≥ 1，循环至少会执行一轮，不存在「一位都没检查就返回真」的空转风险。

判定内部的短路顺序同样要固定：先判 d == 0，再判 num % d != 0。这两个条件用逻辑或连接，靠短路求值保证了 d 为 0 时绝不会执行 num % d。把顺序写反，遇到含 0 的数就是除零异常，而不是返回 false。

外层就简单了：从 left 递增到 right（闭区间，条件用 <=），判定为真就追加进结果列表。结果列表天然按升序排列，因为枚举顺序就是升序，不需要额外排序。

解题步骤

第一步，准备结果容器。 为什么要显式初始化成空列表而不是留 null：题目要求返回一个列表，区间内一个自除数都没有时（例如 [80, 87]，因为 80 含 0、81 不被 8 整除、82 到 87 逐一都不合格）必须返回空列表。Go 里用 make([]int, 0) 而不是声明一个 nil 切片，是为了让 JSON 序列化出来是 [] 而不是 null。

第二步，外层从 left 循环到 right，条件写 x <= right。 为什么用 <=：区间是闭的，右端点本身也是候选。这是最容易被顺手写成 < 的地方。

第三步，进入判定函数时先把参数复制到工作变量。 为什么必须复制：接下来的剥位会不断做 x /= 10，如果直接在参数上操作，第二轮开始被除数就变成了截断后的数，判定语义完全改变。这一行赋值就是「原值与副本分离」不变量的载体。

第四步，循环取末位 d = x % 10，先查 d == 0，再查 num % d != 0，任一成立立刻返回假。 为什么先查 0：短路求值让除零永远不会发生，这不是风格问题而是正确性问题。为什么用 num 做被除数：题目要求的是原数被每一位整除。

第五步，一轮检查通过后 x /= 10 剥掉已检查的末位。 为什么整除 10 而不是取字符串下标：整除法不需要额外内存也不涉及字符转换，是数位遍历的标准手法；顺带一提它天然从低位向高位走，而本题的判定与位的顺序无关，所以方向不重要。

第六步，x 归零后所有位都已通过检查，返回真；外层据此把该数追加进结果。

以 left = 45、right = 50 走一遍。

x = 45：副本置 45，取末位 d = 5，非 0 且 45 % 5 == 0，通过；剥位后副本变 4，取末位 d = 4，非 0 但 45 % 4 == 1，不整除，返回假。注意这里用的是 45 % 4 而非 4 % 4——如果误用副本做被除数，4 % 4 == 0 会让 45 被错判成自除数。这个用例正好卡住那个 bug。

x = 46：d = 6，46 % 6 == 4，返回假。

x = 47：d = 7，47 % 7 == 5，返回假。

x = 48：d = 8，48 % 8 == 0，通过；副本变 4，d = 4，48 % 4 == 0，通过；副本变 0，循环结束，返回真。48 加入结果。

x = 49：d = 9，49 % 9 == 4，返回假。

x = 50：d = 0，第一个条件即命中，直接返回假。若把两个条件的顺序写反，这里就会先算 50 % 0 并抛出算术异常。

循环在 x = 50 处满足 50 <= 50 后结束，返回 [48]。若外层条件误写成 x < right，50 不会被检查——本例中恰好不影响答案，但把区间换成 [45, 48] 就会丢掉 48 这个正确答案。

代码实现

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
}

复杂度分析

时间复杂度：$O((right - left + 1) \cdot \log_{10} right)$。外层枚举区间内每个整数，内层剥位的轮数等于该数的十进制位数，即 $\log_{10}$ 量级。在 $right \le 10^4$ 的约束下，总操作量不超过 $10^4 \times 5 = 5 \times 10^4$，常数极小。

空间复杂度：$O(1)$ 额外空间。判定函数只用了 x 和 d 两个整型变量，与输入规模无关；结果列表的长度由答案个数决定，属于必须返回的输出而不计入额外空间。

关键点总结

原值与工作副本必须分离。凡是「按位/按元素拆解某个对象，同时又要引用这个对象整体」的题，都要给拆解过程单开一个副本。本题里 num 是被除数、x 是游标，两者职责不能重叠——这是可以直接迁移到数位 DP、数字反转、回文数判定的通用纪律。

短路求值可以承担防御职责。d == 0 || num % d != 0 里，前半部分不只是业务规则，还是后半部分的前置守卫。习惯性地把「让运算合法的条件」排在「运算本身」之前，能消除一整类除零、空指针、越界错误。

整除 10 是遍历数位的标准姿势。x % 10 取末位、x /= 10 去末位、x > 0 作为终止条件，这三件套比转字符串更省内存也更不容易出错，值得形成肌肉记忆。

约束小到不需要优化时，就把力气花在结构清晰上。$10^4$ 的规模明确排除了打表、筛法、预处理的必要性。识别出「这题不考优化」本身就是一种能力，避免把简单题做复杂。

面试视角：这是典型的暖场题，面试官真正在看三件事——你是否读准了「被除数是原数」这个定义、你是否在做除法前挡住了 0、你的判定逻辑是否被抽成了独立函数。主动说出「我把单数判定抽成纯函数，这样外层枚举和内层规则可以各自独立验证」比闷头写完更能拿分。如果被追问「区间放大到 $10^9$ 怎么办」，正确回应是：自除数在大范围内极其稀疏，可以改为按位构造候选数（每位只能取 1 到 9）再回验，而不是继续逐个枚举。

返回空集合而非 null。这类「筛选后返回列表」的题，无结果时的返回值语义要在动手前就定好，它属于接口契约的一部分，而不是边界特判。

易错点总结

错误写法：整除判断用副本 x % d 而不是原值 num % d。以 [45, 45] 为例，剥到第二位时副本已是 4，4 % 4 == 0 通过，45 被错判为自除数，返回 [45]，而正确答案是 []。这是本题第一大错误，且大量用例（如 48、55）在两种写法下结果相同，很难靠随手测试发现。

错误写法：判定函数直接在参数上做 num /= 10，不另设副本。以 [128, 128] 为例，第一轮 d = 8 时 128 % 8 == 0 通过，随后 num 变成 12，第二轮 d = 2 检查的是 12 % 2，第三轮检查 1 % 1，全部通过返回真——碰巧结果正确；但换成 [45, 45] 就会返回 [45]，同样是错的。参数被就地修改是隐蔽 bug 的温床。

错误写法：两个条件顺序写反成 num % d != 0 || d == 0。以 [50, 50] 为例，先计算 50 % 0，Java 抛 ArithmeticException: / by zero，Go 触发 integer divide by zero panic，程序直接崩溃而不是返回空列表。

错误写法：外层循环条件写成 x < right。以 [45, 48] 为例，48 不会被检查，返回 []，而正确答案是 [48]。闭区间漏掉右端点是这类枚举题的高频笔误。

错误写法：剥位循环条件写成 x >= 0。以 [11, 11] 为例，剥完两位后 x 变为 0，循环仍继续，取出 d = 0，命中「含 0」分支返回假，11 被错判，返回 []，正确答案是 [11]。更糟的是若没有 0 的判断，还会陷入 0 / 10 == 0 的死循环。

错误写法：只在最后统一判断「原数是否包含 0」，剥位时不查 d == 0。以 [102, 102] 为例，若先算 102 % 2 == 0 通过、再算 102 % 0 就已经崩了；即便调换顺序侥幸不崩，也多了一次完整的字符串或数位扫描，属于把一个判断拆成两处的坏结构。

错误写法：Go 里返回未初始化的 nil 切片 var answer []int。以 [80, 87] 为例（区间内无自除数），返回的是 nil，判题系统序列化成 null 而非 []，部分测试会判错。Java 侧对应的错误是返回 null 引发调用方空指针。

错误写法：把判定改成先转字符串再逐字符取值，但忘记字符与数字的转换。以 [12, 12] 为例，若直接用字符 '1'（ASCII 49）做除数，12 % 49 == 12 不为 0，12 被错判为非自除数，返回 []，正确答案包含 12。字符转数字必须减去 '0'。

错误写法：以为区间内的数递增就可以在遇到第一个非自除数时提前结束。以 [45, 48] 为例，45 不合格但 48 合格，一旦提前返回就会丢掉 48。自除数在数轴上完全没有单调性或连续性，任何提前终止的剪枝都是错的。

错误写法：对结果列表再做一次排序。以 [1, 22] 为例，结果本就是 [1,2,3,4,5,6,7,8,9,11,12,15,22] 的升序，额外排序不影响正确性但徒增 $O(k \log k)$ 开销，面试中会被追问「为什么需要排序」而答不上来。

相似题目

题目	难度	考察点
9. 回文数	简单	同样靠取模除十遍历数位，但要反转一半数字并与剩余部分比对
7. 整数反转	中等	剥位后要重新拼装，核心难点转为 32 位溢出的提前检测
258. 各位相加	简单	需反复求数位和直到个位，可用数根公式 $O(1)$ 收敛
202. 快乐数	简单	数位平方和会形成环，判定重点从整除变成用快慢指针检测循环
507. 完美数	简单	检查的是因子之和而非各位数字，枚举范围可缩到 $\sqrt{n}$
738. 单调递增的数字	中等	不是判定而是构造，需从高位贪心地借位并把后缀全置 9
357. 统计各位数字都不同的数字个数	中等	规模大到无法枚举，改用按位排列组合直接计数
172. 阶乘后的零	中等	同为数论小题，但要转化成统计因子 5 的个数，考察问题等价变换