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

标签: 贪心位运算数组

难度: Medium

给你一个只包含非负整数的数组 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 <= 10⁵
0 <= nums[i] <= 10⁶

Submission

运行时间: 77 ms

内存: 24.8 MB

'''
AND 性质：两个不同的数 a and b < max(a, b)
a and 0 = 0
参与 and 的数越多 结果越小 
'''


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

Explain

题解通过遍历数组元素，并连续地对它们进行AND操作，直到结果变为0。一旦结果为0，意味着可以形成一个子数组，因此增加子数组的计数。然后重置AND操作的初始值重新开始。这个策略利用了AND操作的属性，即任何数与0进行AND操作的结果都为0。因此，最优策略是尽可能快地达到AND结果为0，从而最大化子数组的数量。整体方法是贪心策略，通过局部最优达到全局最优，即尽可能分割出多的子数组，使得每个子数组的AND结果尽可能小（优先达到0）。最后，如果数组中的所有元素AND的结果不为0，则至少可以形成1个子数组。

时间复杂度: O(n)

空间复杂度: O(1)

'''
AND 性质：两个不同的数 a and b < max(a, b)
a and 0 = 0
参与 and 的数越多 结果越小 
'''


class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        ans = 0  # 子数组计数
        a = -1  # 初始AND结果设为全1的二进制（-1在二进制中表示全1）
        for x in nums:
            a &= x  # 对当前元素进行AND操作
            if a == 0:  # 如果AND结果为0，可以形成一个子数组
                ans += 1  # 增加子数组计数
                a = -1  # 重置AND操作的初始值，开始新的子数组
        return max(ans, 1)  # 如果没有任何子数组AND结果为0，则至少有一个子数组

Explore

在AND操作中，一旦结果变为0，意味着至少有一位在所有参与AND运算的元素中均为0。由于更多的元素参与AND运算只会让结果的位中的1变成0（从不会从0变回1），所以一旦达到0，继续添加新的元素不会让AND结果变回非0。因此，在结果首次变为0时形成一个子数组是合理的，这确保了在当前子数组的范围内，元素的AND结果是最小的（即0）。

如果数组中的一个数为0，则根据算法逻辑，该数与之前的AND结果进行AND运算后得到0。在这种情况下，算法会立即结束当前子数组的构建，并开始一个新的子数组。这是因为0与任何数进行AND运算的结果仍然为0，所以以0为分界点开始新的子数组是最优的分割方式。

变量`a`被初始化为-1，确实假设了所有整数的位宽相同，通常是32位。在-1的二进制表示中，所有位都是1。这种初始化方法在所有整数位宽相同的情况下是有效的，因为它代表了最大可能的位值。如果处理的整数位宽不同，这种方法可能不适用，因为对于更长的位宽，-1的表示将包含更多的1位，可能导致错误的AND结果。在这种情况下，应该根据实际的最大位宽来调整初始化的值。

算法确实考虑了数组中所有元素AND结果不为0的情况。如果在整个数组遍历结束后，AND结果仍然不为0，算法通过确保至少返回1来处理这种情况。这意味着即便不能通过将AND结果变为0来进一步分割数组，至少整个数组可以作为一个子数组。这种方法确保了在无法通过AND操作进一步细分的情况下，至少有一个子数组，但不一定是最多的子数组数目，因为算法的目标是尽可能使AND结果尽快达到0，从而最大化子数组数量。