LeetCode 每日一题笔记
0. 前言
- 日期：2025.11.24
- 题目：1018. 可被5整除的二进制前缀
- 难度：简单
- 标签：数组 位运算 模运算
1. 题目理解
问题描述：
给定一个二进制数组 nums（索引从 0 开始），定义 xi 为子数组 nums[0..i] 对应的二进制数（从最高有效位到最低有效位）。返回布尔值列表 answer，其中 answer[i] 为 true 当且仅当 xi 可被 5 整除，否则为 false。
关键细节：
- 二进制数组的每个元素仅为 0 或 1；
- 子数组
nums[0..i]是从第 0 位到第 i 位的连续前缀，并非任意子数组； - 需注意二进制数的进位逻辑：新增一位时，原数左移 1 位（等价于 ×2）再加新位的值（0 或 1）。
示例解析：
示例 1：
输入：nums = [0,1,1]
- x0 = 0 → 0 ÷ 5 = 0 → answer[0] = true
- x1 = 0×2 + 1 = 1 → 1 ÷ 5 余 1 → answer[1] = false
- x2 = 1×2 + 1 = 3 → 3 ÷ 5 余 3 → answer[2] = false
输出：[true,false,false]
示例 2：
输入：nums = [1,1,1]
- x0 = 1 → 余 1 → false
- x1 = 1×2 + 1 = 3 → 余 3 → false
- x2 = 3×2 + 1 = 7 → 余 2 → false
输出：[false,false,false]
2. 解题思路
核心观察
- 直接计算
xi的十进制值会导致 数值溢出：当数组长度较长（如超过 32 位）时，xi会超出int甚至long的范围，无法直接存储； - 模运算性质：
(a × 2 + b) % 5 = [(a % 5) × 2 + b] % 5。即：当前前缀的模 5 结果，可由前一个前缀的模 5 结果推导得出，无需计算完整数值； - 最终只需判断当前前缀的模 5 结果是否为 0，即可确定是否能被 5 整除。
算法步骤
- 初始化变量
current为 0，用于存储当前前缀的模 5 结果（始终保持current < 5，避免溢出）； - 遍历二进制数组
nums的每个元素num（0 或 1）：- 计算新前缀的模 5 结果：
current = (current × 2 + num) % 5（利用模运算性质，避免大数）； - 判断
current是否为 0，将结果（true/false）加入答案列表；
- 计算新前缀的模 5 结果：
- 遍历结束后，返回答案列表。
3. 代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {List<Boolean> result = new ArrayList<>();int current = 0; // 存储当前前缀对5取模的结果，始终 <5for (int num : nums) {// 核心公式：新前缀 = 原前缀×2 + 新位，取模5避免溢出current = (current * 2 + num) % 5;// 模5为0则可整除，直接添加布尔结果result.add(current == 0);}return result;}}4. 代码优化说明
原始暴力思路（不可行）
最初可能想到“每次重新计算前缀的十进制值”，代码如下：
// 错误示例：数值溢出，仅适用于短数组
List<Boolean> result = new ArrayList<>();for (int i = 0; i < nums.length; i++) {int res = 0;for (int j = 0; j <= i; j++) {res += nums[j] * (1 << (i - j)); // 左移计算二进制值，超长数组会溢出}result.add(res % 5 == 0);}- 问题：当
i ≥ 31时，1 << (i - j)会超出int范围，导致数值溢出，结果错误； - 时间复杂度：O(n²)，效率低下。
优化点
- 空间优化：无需存储完整前缀值，仅保留模 5 结果（
current始终为 0-4 的整数），空间复杂度从 O(n) 降至 O(1)（除答案列表外）； - 时间优化：遍历一次数组即可，时间复杂度从 O(n²) 降至 O(n)；
- 避免溢出：利用模运算性质，确保中间结果始终在 0-4 之间，彻底解决溢出问题。
5. 复杂度分析
- 时间复杂度：O(n)，其中 n 为数组
nums的长度。仅需遍历数组一次，每次迭代执行 O(1) 操作； - 空间复杂度：O(1)（额外空间）。除了存储答案的列表
result（空间复杂度 O(n)，为输出必需），仅使用常数级别的临时变量current。
6. 总结
- 本题的核心是 利用模运算性质规避数值溢出，这是处理“大数取模”类问题的常用技巧；
- 关键思路：无需计算完整的二进制数，只需通过前一个状态的模结果推导当前状态，既高效又安全；
- 延伸思考：类似问题（如“可被 3 整除的二进制前缀”“可被 7 整除的前缀”）均可复用此思路，只需将模运算的除数替换为对应数值；
- 注意细节：二进制数的进位逻辑（左移 ×2 加新位）是推导公式的基础，需准确理解前缀的数值变化规律。