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

题目

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

---

给你一个下标从 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^5
• 0 <= nums[i] < 2^30
• 0 <= k < nums.length

题解

方法一：

思路

初始化答案为ans=(1<<30)-1，三十位二进制全为1。

从高位起尝试置为0，当前构造的ans检测是否可行，

每次通过贪心的方式检测，当一段连续的区间内的数与和中，某位为1则对应的ans的位不应该为0，否则这段区间没有满足。一旦满足了一段区间则可以减少一次操作。最后操作次数不大于k当前位构造0是合法的。

代码

class Solution {
public:
    int minOrAfterOperations(vector<int>& nums, int k) {
    	auto check = [&](int msk) {
            int c = (1<<30)-1;
            int opt = 0; //操作次数
            for (int i:nums) {
                c &= i;
            	int ok = 1;
                for (int j=0; j<30; j++) {
                    if ((c>>j&1)==1 && (msk>>j&1)==0) {
                        ok = 0;
                    }
                }
				if (ok) {
                    c = (1<<30)-1;
                } else {
                	opt++;
                }
            }
			// cout << msk << " " << opt << endl;

			return opt <= k;
        };
        int msk = (1<<30)-1;
        for (int i=29; i>=0; i--) {
			if (check(msk ^ (1<<i))) {
               msk ^= (1<<i);
            }
        }
        return msk;
    }
};