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

01 Sep 2024 in Algorithm Pageviews

leetcode

给你一个下标从 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 次操作以内，可以得到的剩余元素的最小按位或值。

代码实现如下:

class Solution {
public:
    int MinOrAfterOperations(vector<int> &nums, int k)
    {
        int ans = 0;
        int mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= 1 << i;
            int flag = 0;
            int res = -1;
            for (int j = 0; j < nums.size(); j++) {
                res &= nums[i] & mask;
                if (res != 0) {
                    flag++;
                } else {
                    res = -1;
                }
            }
            
            // 超过k次操作，清除mask掩码
            if (flag > k) {
                ans |= 1 << i;
                mask &= ~1 << i;
            }
        }
        return res;
    }
};