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:
题目来自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完整代码如下:
package main
import (
"fmt"
)
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
}
func main() {
nums := []int{3, 5, 3, 2, 7}
k := 2
fmt.Println(minOrAfterOperations(nums, k))
}
Python完整代码如下:
# -*-coding:utf-8-*-
def min_or_after_operations(nums, k):
ans = 0
mask = 0
for b in range(29, -1, -1):
mask |= 1 << b
cnt = 0 # 操作次数
and_op = -1 # -1 的二进制全为 1
for x in nums:
and_op &= x & mask
if and_op != 0:
cnt += 1 # 合并 x,操作次数加一
else:
and_op = -1 # 准备合并下一段
if cnt > k:
ans |= 1 << b # 答案的这个比特位必须是 1
mask ^= 1 << b # 后面不考虑这个比特位
return ans
nums = [3, 5, 3, 2, 7]
k = 2
print(min_or_after_operations(nums, k))
标签:nums,mask,整数,按位,数组,ans,操作
From: https://www.cnblogs.com/moonfdd/p/18256759