Easy

题目描述

给定一个二进制数组 nums（下标从 0 开始）。

我们定义 xi 为数组 nums[0..i]（从最高位到最低位）的二进制表示对应的数字。

例如，如果 nums = [1,0,1]，那么 x0 = 1，x1 = 2，x2 = 5。

返回布尔数组 answer，其中 answer[i] 为 true 当且仅当 xi 能被 5 整除。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：输入的二进制数字分别是 0, 01, 011；对应十进制数字是 0, 1, 3。
只有第一个数字能被 5 整除，所以 answer[0] 为 true。

示例 2：

输入：nums = [1,1,1]
输出：[false,false,false]

约束条件：

  • 1 <= nums.length <= 10^5
  • nums[i] 是 0 或 1

提示：

  • 如果 X 是数组前 i 位的二进制数，那么 2X + nums[i] 是前 i+1 位的二进制数。

解题思路

这道题的关键是理解二进制数的构建过程。当我们从左到右遍历数组时，每添加一个新位，相当于将当前数字左移一位（乘以2）再加上新位的值。

核心思路：

  • 设当前的十进制数为 current，下一位为 nums[i]
  • 则新的十进制数为 current * 2 + nums[i]
  • 判断新数是否能被5整除

优化关键：由于题目只关心是否能被5整除，我们不需要存储完整的十进制数值。根据模运算性质：(a * b + c) % 5 = ((a % 5) * (b % 5) + c % 5) % 5

因此我们只需要维护当前数对5的余数即可：

  • remainder = (remainder * 2 + nums[i]) % 5
  • 如果 remainder == 0，说明当前数能被5整除

这样做的好处是避免了大数运算的问题，因为数组长度可能很长，完整的二进制数会超出整型范围。

时间复杂度为 O(n)，空间复杂度为 O(1)（不计算返回数组）。

代码实现

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector<bool> result;
        int remainder = 0;
        
        for (int num : nums) {
            remainder = (remainder * 2 + num) % 5;
            result.push_back(remainder == 0);
        }
        
        return result;
    }
};

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        result = []
        remainder = 0
        
        for num in nums:
            remainder = (remainder * 2 + num) % 5
            result.append(remainder == 0)
        
        return result

public class Solution {
    public IList<bool> PrefixesDivBy5(int[] nums) {
        var result = new List<bool>();
        int remainder = 0;
        
        foreach (int num in nums) {
            remainder = (remainder * 2 + num) % 5;
            result.Add(remainder == 0);
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean[]}
 */
var prefixesDivBy5 = function(nums) {
    let result = [];
    let remainder = 0;
    
    for (let i = 0; i < nums.length; i++) {
        remainder = (remainder * 2 + nums[i]) % 5;
        result.push(remainder === 0);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组，n 为数组长度
空间复杂度O(1)只使用常数级别的额外空间（不计算返回数组）

相关题目