2024-06-19：用go语言，给定一个起始下标为 0 的整数数组 nums 和一个整数 k，
可以执行一个操作将相邻两个元素按位AND后替换为结果。
要求在最多执行 k 次操作的情况下，
计算数组中所有元素按位OR后的最小值。
输入：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 次操作以内，可以得到的剩余元素的最小按位或值。
答案2024-06-19：
chatgpt
题目来自leetcode3022。
大体步骤如下：
1.使用一个循环从最高位（第 29 位）到最低位（第 0 位）来考虑每个比特位。
2.对于每个比特位 b，首先创建一个掩码 mask，初始为 0。在每次循环中通过将 1 左移 b 位来设置当前考虑的比特位为 1。
3.创建计数变量 cnt 来记录操作次数，初始设为 0。也创建一个变量 and 初始化为 -1（所有位均为 1）。
4.遍历数组中的每个数字 x：
- •将当前 and 与 x 按位与并存储结果到 and 中。
- •如果 and 不为 0，增加操作次数 cnt；否则重置 and 为 -1，准备处理下一段。
5.如果计数 cnt 大于 k，则将答案 ans 的第 b 位设置为 1，同时更新掩码 mask，排除当前位。
6.重复以上步骤直至处理到最低位（第 0 位）。
7.返回最终结果 ans，即所有元素按位 OR 后的最小值。
总的时间复杂度：O(N), 其中 N 为数组的长度，因为对每个元素进行了一次遍历。 总的额外空间复杂度：O(1)，因为只使用了常数个额外变量来存储操作的中间结果，没有使用随数组长度变化的额外空间。
Go完整代码如下：
packagemain
import(
"fmt"
)
funcminOrAfterOperations(nums[]int,kint)(ansint){
mask:=0
forb:=29;b>=0;b--{
mask|=1<cnt:=0//操作次数
and:=-1//-1的二进制全为1
for_,x:=rangenums{
and&=x&mask
ifand!=0{
cnt++//合并x，操作次数加一
}else{
and=-1//准备合并下一段
}
}
ifcnt>k{
ans|=1<mask^=1<}
}
return
}
funcmain(){
nums:=[]int{3,5,3,2,7}
k:=2
fmt.Println(minOrAfterOperations(nums,k))
}
Python完整代码如下：
#-*-coding:utf-8-*-
defmin_or_after_operations(nums,k):
ans=0
mask=0
forbinrange(29,-1,-1):
mask|=1<cnt=0#操作次数
and_op=-1#-1的二进制全为1
forxinnums:
and_op&=x&mask
ifand_op!=0:
cnt+=1#合并x，操作次数加一
else:
and_op=-1#准备合并下一段
ifcnt>k:
ans|=1<mask^=1<returnans
nums=[3,5,3,2,7]
k=2
print(min_or_after_operations(nums,k))
热门跟贴