leetcode
leetcode 951 ~ 1000
可被 5 整除的二进制前缀

可被 5 整除的二进制前缀

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 17.5 MB


/* 
 * 思路:
 * 使用Java Stream API,我们依然需要遍历数组并计算从0到i的二进制子数组的数值。
 * 我们可以用Stream.iterate来生成一个索引流,并在forEach中进行计算和更新。 
 */
import java.util.stream.*;
public List<Boolean> prefixesDivBy5Stream(int[] nums) {
    int[] num = {0}; // 用数组包装以便在lambda中修改
    return IntStream.range(0, nums.length)
            .mapToObj(i -> {
                num[0] = ((num[0] << 1) | nums[i]) % 5;
                return num[0] == 0;
            })
            .collect(Collectors.toList());
}

解释

方法:

这个题解使用了迭代的方法来计算每个前缀的二进制数对应的十进制数是否可以被5整除。在每次迭代中,它将之前的前缀数左移一位(相当于乘以2),然后加上当前的数字,得到新的前缀数。由于只关心这个数是否能被5整除,所以可以对每次得到的新前缀数取模5,这样可以防止数值过大。最后,判断当前的前缀数是否为0,如果为0则表示可以被5整除,将True添加到结果列表中,否则添加False。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算二进制数字的十进制表示时,只取模5的结果,而不是完整的十进制数?
在这个问题中,我们只关心二进制前缀转换成的十进制数是否能被5整除。计算完整的十进制数在大数组或长二进制序列情况下可能导致非常大的数值,这不仅会增加计算的复杂度,还可能导致整数溢出。通过仅保留模5的结果,我们可以显著降低数值的大小,同时保持能否被5整除的这一特性不变,因为一个数被5整除的性质仅依赖于它除以5的余数。
🦆
在处理很大的数组时,即使取模5,prefix变量是否有溢出的风险?
由于在每次迭代中,计算结果都取模5,因此prefix的值始终在0到4之间。这样的处理显著减少了数值的大小,避免了整数溢出的风险。Python中整数类型可以自动处理较大的数(自动转换为长整型),但在一些其他编程语言中,未经处理的大整数可能导致溢出。在这种情况下,取模操作是防止溢出的有效策略。
🦆
题解中提到的操作`prefix = ((prefix << 1) + num) % 5`,这里的左移操作是如何影响计算结果的?
左移操作(<<)在二进制数中相当于将数值乘以2。例如,如果二进制数为`101`(十进制5),左移一位后变为`1010`(十进制10)。这个操作在构建二进制数的过程中非常关键,因为每遇到一个新的二进制位,之前的数值都需要左移(即乘以2),然后加上新的位(0或1)。这样可以从左到右逐步构建出完整的二进制数。取模5是在此基础上应用,以保持数值管理在一个较小的范围内。
🦆
为什么在判断是否能被5整除时,直接使用`prefix == 0`,这样的判断是否总是准确的?
在数学中,一个数如果能被另一个数整除,那么其除以那个数的余数必定为0。在题解中使用`prefix == 0`来判断是否能被5整除是基于这个数学原理的。因为prefix变量在每一步都执行了取模5的操作,所以prefix的值是当前二进制前缀对应的十进制数除以5的余数。当这个余数为0时,说明当前的二进制前缀可以被5整除,因此这种判断是准确的。

相关问题