可被 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,prefix变量是否有溢出的风险?
▷🦆
题解中提到的操作`prefix = ((prefix << 1) + num) % 5`,这里的左移操作是如何影响计算结果的?
▷🦆
为什么在判断是否能被5整除时,直接使用`prefix == 0`,这样的判断是否总是准确的?
▷