Question

2871. 将数组分割成最多数目的子数组

English Version

题目描述

给你一个只包含 非负 整数的数组 nums 。

我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

• 每个 元素都 只 属于一个子数组。
• 子数组分数之和尽可能 小 。

请你在满足以上要求的条件下，返回 最多 可以得到多少个子数组。

一个 子数组 是一个数组中一段连续的元素。

 

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 106

解法

方法一：贪心 + 位运算

我们初始化一个变量 $score$，用来记录当前子数组的分数，初始时 $score = -1$。然后我们遍历数组，对于每个元素 $num$，我们将 $score$ 与 $num$ 进行按位与运算，然后将结果赋值给 $score$。如果 $score = 0$，说明当前子数组的分数为 $0$，我们就可以将当前子数组分割出来，然后将 $score$ 重置为 $-1$。最后我们返回分割出的子数组的个数。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

class Solution:
  def maxSubarrays(self, nums: List[int]) -> int:
    score, ans = -1, 1
    for num in nums:
      score &= num
      if score == 0:
        score = -1
        ans += 1
    return 1 if ans == 1 else ans - 1

class Solution {
  public int maxSubarrays(int[] nums) {
    int score = -1;
    int ans = 1;
    for (int num : nums) {
      score &= num;
      if (score == 0) {
        ans++;
        score = -1;
      }
    }
    return ans == 1 ? 1 : ans - 1;
  }
}

class Solution {
public:
  int maxSubarrays(vector<int>& nums) {
    int score = -1, ans = 1;
    for (int num : nums) {
      score &= num;
      if (score == 0) {
        --score;
        ++ans;
      }
    }
    return ans == 1 ? 1 : ans - 1;
  }
};

func maxSubarrays(nums []int) int {
  ans, score := 1, -1
  for _, num := range nums {
    score &= num
    if score == 0 {
      score--
      ans++
    }
  }
  if ans == 1 {
    return 1
  }
  return ans - 1
}

function maxSubarrays(nums: number[]): number {
  let [ans, score] = [1, -1];
  for (const num of nums) {
    score &= num;
    if (score === 0) {
      --score;
      ++ans;
    }
  }
  return ans == 1 ? 1 : ans - 1;
}