class Solution {
public:
int minOrAfterOperations(vector<int>& nums, int k) {
}
};
100179. 给定操作次数内使剩余元素的或值最小
给你一个下标从 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 <= 1050 <= nums[i] < 2300 <= k < nums.length原站题解
golang 解法, 执行用时: 122 ms, 内存消耗: 8.7 MB, 提交时间: 2024-01-28 23:41:48
func minOrAfterOperations(nums []int, k int) (ans int) {
mask := 0
for b := 29; b >= 0; b-- {
mask |= 1 << b
cnt := 0 // 操作次数
and := -1 // -1 的二进制全为 1
for _, x := range nums {
and &= x & mask
if and != 0 {
cnt++ // 合并 x
} else {
and = -1 // 准备合并下一段
}
}
if cnt > k {
ans |= 1 << b // 答案的这个比特位必须是 1
mask ^= 1 << b // 后面不考虑这个比特位
}
}
return
}
java 解法, 执行用时: 47 ms, 内存消耗: 55.1 MB, 提交时间: 2024-01-28 23:41:36
class Solution {
public int minOrAfterOperations(int[] nums, int k) {
int ans = 0;
int mask = 0;
for (int b = 29; b >= 0; b--) {
mask |= 1 << b;
int cnt = 0; // 操作次数
int and = -1; // -1 的二进制全为 1
for (int x : nums) {
and &= x & mask;
if (and != 0) {
cnt++; // 合并 x
} else {
and = -1; // 准备合并下一段
}
}
if (cnt > k) {
ans |= 1 << b; // 答案的这个比特位必须是 1
mask ^= 1 << b; // 后面不考虑这个比特位
}
}
return ans;
}
}
cpp 解法, 执行用时: 138 ms, 内存消耗: 70.2 MB, 提交时间: 2024-01-28 23:41:25
class Solution {
public:
int minOrAfterOperations(vector<int> &nums, int k) {
int ans = 0, mask = 0;
for (int b = 29; b >= 0; b--) {
mask |= 1 << b;
int cnt = 0, and_res = -1; // -1 的二进制全为 1
for (int x : nums) {
and_res &= x & mask;
if (and_res) {
cnt++; // 合并 x，操作次数加一
} else {
and_res = -1; // 准备合并下一段
}
}
if (cnt > k) {
ans |= 1 << b; // 答案的这个比特位必须是 1
mask ^= 1 << b; // 后面不考虑这个比特位
}
}
return ans;
}
};
python3 解法, 执行用时: 742 ms, 内存消耗: 29.7 MB, 提交时间: 2024-01-28 23:41:12
class Solution:
def minOrAfterOperations(self, nums: List[int], k: int) -> int:
ans = mask = 0
for b in range(max(nums).bit_length() - 1, -1, -1):
mask |= 1 << b
cnt = 0 # 操作次数
and_res = -1 # -1 的二进制全为 1
for x in nums:
and_res &= x & mask
if and_res:
cnt += 1 # 合并 x
else:
and_res = -1 # 准备合并下一段
if cnt > k:
ans |= 1 << b # 答案的这个比特位必须是 1
mask ^= 1 << b # 后面不考虑这个比特位
return ans