leetcode
leetcode 601 ~ 650
自除数

自除数

难度:

标签:

题目描述

代码结果

运行时间: 28 ms, 内存: 15.9 MB


/*
 * 题目思路:
 * 使用Java Stream API实现自除数的判断和筛选。
 * Stream可以简化代码的编写,通过流操作来实现过滤和收集。
 * 这里我们使用rangeClosed来生成[left, right]范围的数字流,
 * 然后过滤掉不是自除数的数字,最后收集到列表中。
 */
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class SelfDividingNumbersStream {
    public static List<Integer> selfDividingNumbers(int left, int right) {
        return IntStream.rangeClosed(left, right)
                .filter(SelfDividingNumbersStream::isSelfDividing)
                .boxed()
                .collect(Collectors.toList());
    }
 
    private static boolean isSelfDividing(int num) {
        int originalNum = num;
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0 || originalNum % digit != 0) {
                return false;
            }
            num /= 10;
        }
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println(selfDividingNumbers(1, 22));
    }
}

解释

方法:

该题解的思路是遍历从 left 到 right 的所有整数,对于每个整数 i,判断它是否是自除数。判断的方法是不断对 i 进行整除 10 的操作,得到每一位数字,然后判断 i 是否能被每一位数字整除。如果出现任何一位数字为 0,或者 i 不能被某一位数字整除,则 i 不是自除数。如果 i 能被它的每一位数字整除,则将其加入到结果列表中。

时间复杂度:

O(n * logr)

空间复杂度:

O(n)

代码细节讲解

🦆
在解决这个问题时,如何处理多位数中包含0的情况,从而保证不会发生除以零的错误?
在算法实现中,对于每一个整数i,通过不断地进行取余操作(use % 10)来获取i的最低位。紧接着进行了一个判断:如果当前位(即 use % 10)为0,则立即将该数标记为非自除数并终止当前数的进一步检查。这样的处理确保了当遇到数字0时,程序不会尝试执行除以0的操作,从而避免了运行错误。
🦆
为什么在判断自除数时采用了从右到左检查每一位数的方法,而不是其他方式?
采用从右到左的方式检查每一位数字主要是因为这种方法可以直接通过取余和整除操作来实现,操作简单且直接。对于整数i,通过不断对10进行取余可以获取当前最低位,之后再通过整除10操作去除最低位,这样可以顺序地检查每一位数。这种方式在实现上不需要额外的数据结构,例如数组或字符串,而且可以即时地判断每一位是否符合自除数的条件,效率较高。
🦆
在题解的算法中,如果输入的范围left和right非常接近,但数值本身很大,比如9990到10000,这种情况下算法的效率如何?
在这种情况下,尽管left和right非常接近,算法仍然需要检查每个数的每一位来确定是否是自除数。对于大数字,这意味着每个数字都需要进行多次除法和取余操作,这可能会导致计算量增大。然而,由于检查的数的范围较小(例如只有11个数字从9990到10000),总体计算量仍然是可管理的。但是,如果区间内的数字都很大且数量较多,算法的性能可能会受到影响。
🦆
如果要扩展这个问题,使其能处理更大范围的数(例如超过10^4),那么现有的算法是否还适用,或者需要哪些优化?
现有的算法在理论上可以处理任何范围的数,但是随着数字大小的增加,每个数字的位数也会增长,这将导致更多的取余和整除操作,从而影响算法的效率。如果要处理更大的数,可以考虑以下优化:1. 使用并行处理技术来同时检查多个数字,特别是在多核处理器上。2. 预先筛选掉包含0的数,因为这些数字一定不是自除数,可以减少不必要的检查。3. 优化数字分解的逻辑,可能通过一些数学技巧减少操作数。4. 考虑使用更高效的编程语言或工具,以便更快地处理大型数据。

相关问题

完美数

对于一个 正整数,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 「完美数」

给定一个 整数 n, 如果是完美数,返回 true;否则返回 false

 

示例 1:

输入:num = 28
输出:true
解释:28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2:

输入:num = 7
输出:false

 

提示:

  • 1 <= num <= 108