Leetcode-1018-可被 5 整除的二进制前缀

题目描述

• 给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。

• 返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。

示例 2：

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

示例 3：

输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]

示例 4：

输入：[1,1,1,0,1]
输出：[false,false,false,false,false

提示：

1 <= A.length <= 30000
A[i] 为 0 或 1

方法 ： 数学归纳法

• 算法思想
  • 首先求出前缀表示的二进制数字
  • 由于数组A很长，每次保留Ni的值，那么数组长度可能导致溢出
  • 由于只需要知道Ni是否可以被5整除，因此在计算的过程中只保留余数即可
  • 余数通项公式可以通过数学归纳法进行证明

---

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        // 1. 初始化结果集和参数
        List<Boolean> list = new ArrayList<Boolean>();
        int prefix = 0;
        int length = A.length;

        // 2. 根据通项判断 mod5 是否成立
        for(int i = 0;i < length;i++){
            prefix = ((prefix << 1) + A[i]) % 5;        // 在计算过程中只需要保留余数即可
            list.add(prefix == 0);                      // 最后判断余数是不是0
        }
        return list;
    }
}

• 复杂度分析
  • 时间复杂度：O(n)，其中 n 是数组 A 的长度。需要遍历数组一次并计算前缀。
  • 空间复杂度：O(1)。除了返回值以外，额外使用的空间为常数。

打赏