2024-06-19：用 go 语言，给定一个起始下标为 0 的整数数组 nums 和一个整数 k，可以执行一个操作将相邻两个元素按位 AND 后替换为结果。要求在最多执行 k 次操作的情况下，计算数组

作者：福大大架构师每日一题

2024-06-19
北京
本文字数：1296 字
阅读完需：约 4 分钟

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 完整代码如下：

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 = 2print(min_or_after_operations(nums, k))