题目描述
给你一个只包含 非负 整数的数组 nums
。
我们定义满足 l <= r
的子数组 nums[l..r]
的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r]
,其中 AND
是按位与运算。
请你将数组分割成一个或者更多子数组,满足:
- 每个 元素都 只 属于一个子数组。
- 子数组分数之和尽可能 小。
请你在满足以上要求的条件下,返回 最多 可以得到多少个子数组。
一个 子数组 是一个数组中一段连续的元素。
样例
输入: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。
输入:nums = [5,7,1,3]
输出:1
解释:我们可以将数组分割成一个子数组:[5,7,1,3],分数为 1,这是可以得到的最小总分数。
在总分数为 1 的前提下,最多可以将数组分割成 1 个子数组。所以返回 1。
限制
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^6
算法
(思维题) $O(n)$
- 首先需要知道子数组分数之和的最小值。由于
AND
操作次数越多,得到的结果会越小,所以将所有数字AND
到一起就可以得到子数组分数之和的最小值。 - 如果这个最小值不是
0
,则答案就是整个数组作为唯一一个子数组,否则,其他分隔方式得到的子数组之和都会大于这个最小值。 - 如果这个最小值为
0
,则可以通过遍历数组,找到尽可能小的子数组段,使其AND
值为0
。
时间复杂度
- 最多遍历数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxSubarrays(vector<int>& nums) {
const int n = nums.size();
int t = INT_MAX;
for (int x : nums)
t &= x;
if (t > 0)
return 1;
int ans = 0;
for (int i = 0, c = INT_MAX; i < n; i++) {
c &= nums[i];
if (c == 0) {
++ans;
c = INT_MAX;
}
}
return ans;
}
};
有个笔误 是得到子数组分组 误写成了刀刀