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

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

第 114 场双周赛 Q3 1750

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

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

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

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

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

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

题解

我的

迷迷糊糊过了...

class Solution {
public:
    int maxSubarrays(vector<int>& nums) {
        // o(n)
        int minn = nums[0];
        for (int& it : nums)
            minn &= it;
        
        int res = 0;
        int now_min = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            now_min &= nums[i];

            if (now_min == minn) {
                ++res;
                if (i + 1 < nums.size())
                    now_min += nums[i + 1]; // 分数之和, 不能超过minn
            }
        }

        return res;
    }
};

C++

0x3f 一次遍历

• AND 的性质是，参与 AND 的数越多，结果越小。

• 子数组的 AND，不会低于整个 $nums$ 数组的 AND。

• 如果 $nums$ 数组的 AND（记作 $a$ ）是大于 $0$ 的，那么只能分割出一个数组（即nums 数组）。根据提示 2，如果分割出超过一个数组，那么得分至少为 $2α$，而这是大于 $a$ 的，不满足「子数组分数之和尽量小」的要求。所以在 $a>0$ 的情况下，答案为 $1$。

• 如果 $nums$ 数组的AND是等于 $O$ 的，那么可以分割出尽量多的AND 等于0 的子数组。怎么分？从左到右遍历数组，只要发现AND等于 $O$ 就立刻分割。如果不立刻分割，由于AND的数越多越能为0，现在多分了一个数，后面就要少分一个数，可能后面就不能为 $0$ 了。注意，如果最后剩下的一段子数组的AND大于 $O$ ，这一段可以直接合并到前一个AND为 $O$ 的子数组中。

class Solution {
public:
    int maxSubarrays(vector<int> &nums) {
        int ans = 0;
        int a = -1; // -1 就是 111...1，和任何数 AND 都等于那个数
        for (int x : nums) {
            a &= x;
            if (a == 0) {
                ans++; // 分割
                a = -1;
            }
        }
        return max(ans, 1); // 如果 ans=0 说明所有数的 and>0，答案为 1
    }
};

// 力扣: 灵神
// https://leetcode.cn/problems/split-array-into-maximum-number-of-subarrays/solutions/2464645/li-yong-and-xing-zhi-yi-ci-bian-li-pytho-p3bj

C++