给定操作次数内使剩余元素的或值最小

难度: Hard

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。

请你返回至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。

示例 1：

输入：nums = [3,5,3,2,7], k = 2
输出：3
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。
3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 2：

输入：nums = [7,3,15,14,2,8], k = 4
输出：2
解释：执行以下操作：
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,15,14,2,8] 。
2. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,14,2,8] 。
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [2,2,8] 。
4. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ，得到 nums 为 [2,0] 。
最终数组的按位或值为 2 。
2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

示例 3：

输入：nums = [10,7,10,3,9,14,9,4], k = 1
输出：15
解释：不执行任何操作，nums 的按位或值为 15 。
15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] < 2³⁰
0 <= k < nums.length

Submission

运行时间: 526 ms

内存: 28.2 MB

# https://leetcode.cn/u/l00/

class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        finalMust = nums[0]
        final = 0
        for num in nums:
            final |= num
            finalMust &= num

        indexIO = 1
        while indexIO <= final: indexIO <<= 1
        finalMask = (indexIO - 1) ^ final

        while indexIO := indexIO >> 1:
            if (final ^ finalMust) & indexIO:
                target = final ^ indexIO # 假设去掉这个数位的 1 的结果
                targetMask = finalMask ^ indexIO # 假设去掉这个数位的 1 的选区蒙版
                ck = 0
                last = targetMask
                for num in nums:
                    last &= num
                    if last: ck += 1
                    else: last = targetMask
                    # if ck > k: break # 负优化剪枝
                if ck <= k:
                    final = target
                    finalMask = targetMask

        return final

Explain

题解的思路是首先计算数组中所有数字的按位或值 `final` 和按位与值 `finalMust`。`finalMust` 表示所有数字的公共为1的位，这些位无论如何操作都无法改变。接着，尝试从 `final` 中移除某些位来最小化结果。使用一个掩码 `finalMask` 来标识哪些位可以被操作。对于每一位，如果它在 `final` 中但不在 `finalMust` 中，尝试将这一位从1变为0，并检查这样的操作是否可行，即在不超过 k 次操作的情况下，能否通过按位与操作将这一位在所有数字中消除。这个过程从最高位开始，依次向下检查每一位。如果某位可以被消除，则更新 `final` 和 `finalMask`。最终 `final` 将会是经过最多 k 次操作后，所有元素的按位或的最小值。

时间复杂度: O(n)

空间复杂度: O(1)

# https://leetcode.cn/u/l00/

import typing

class Solution:
    def minOrAfterOperations(self, nums: typing.List[int], k: int) -> int:
        # 初始化必须保留的位（AND 所有数字）和当前所有位的 OR 结果
        finalMust = nums[0]
        final = 0
        for num in nums:
            final |= num
            finalMust &= num

        # 初始化最高有效位
        indexIO = 1
        while indexIO <= final: indexIO <<= 1
        # 初始化可操作位掩码
        finalMask = (indexIO - 1) ^ final

        # 逐位检查是否可以把当前位从1变为0
        while indexIO := indexIO >> 1:
            if (final ^ finalMust) & indexIO:
                # 计算假设当前位为0后的新 OR 结果和掩码
                target = final ^ indexIO
                targetMask = finalMask ^ indexIO
                ck = 0
                last = targetMask
                for num in nums:
                    last &= num
                    if last: ck += 1
                    else: last = targetMask
                # 如果在不超过 k 次操作内可以实现，则更新结果和掩码
                if ck <= k:
                    final = target
                    finalMask = targetMask

        return final

Explore

在位运算中，AND操作（按位与）的结果是只有当所有操作数在某一位上都为1时，结果才为1。因此，如果在`finalMust`中某一位是1，意味着数组中所有数字在这一位上都为1。尝试使用AND操作改变这一位时，无论如何与其他数进行AND操作（即使是与0操作），只要数组中的所有数在这一位上原本都为1，结果仍然为1。这就是为什么这些公共为1的位无法通过AND操作改变的原因。

`finalMask` 是通过计算 `(indexIO - 1) ^ final` 得到的，其中 `indexIO` 是大于 `final` 最大位的最小的2的幂。这个掩码的每一位被设置为1，表示相应的位在 `final` 中是0（即可以尝试将其变为0），设置为0则表示该位在 `final` 中为1但不在 `finalMust` 中，即这些位可能通过操作被改变。通过这样的掩码，我们可以快速识别出哪些位是可操作的，从而在算法中对这些位进行特定的处理。

循环通过将 `indexIO` 不断右移（除以2），从而逐步检查从最高位到最低位的每一个位。循环开始前，`indexIO` 被初始化为大于 `final` 最高位的最小2的幂，确保从最高位开始检查。因此，在循环中，每次迭代都会将 `indexIO` 右移一位，依次检查每一位，直到 `indexIO` 变为0。这样的循环结构确保了每一位都会被检查一次，没有遗漏。

异或操作（XOR）具有这样的特性：对于任何位，如果两个操作数的相应位相同则结果为0，不同则为1。在给定的题解算法中，`final ^ indexIO` 的操作用来尝试将 `final` 中的某一位从1改为0（如果该位原来是1）。类似地，`finalMask ^ indexIO` 用于更新掩码，即如果原来这一位在掩码中为0（即在 `final` 中为1），通过异或操作后这一位会变为1，表示这一位已被操作尝试改变。这种方法的依据是异或操作的位反转特性，非常适用于此类位操作场景。