Hard

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

在一次操作中，你可以选择 nums 的任意下标 i，满足 0 <= i < nums.length - 1，并将 nums[i] 和 nums[i + 1] 替换为单个元素 nums[i] & nums[i + 1]，其中 & 表示按位与运算符。

返回在执行 最多 k 次操作后，nums 中剩余元素按位或的 最小可能值。

示例 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。
可以证明，在执行最多 k 次操作后，nums 中剩余元素按位或的最小可能值是 3。

示例 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。

示例 3：

输入：nums = [10,7,10,3,9,14,9,4], k = 1
输出：15
解释：不执行任何操作，nums 的按位或为 15。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^30
  • 0 <= k < nums.length

解题思路

这道题的核心思想是贪心策略：尽可能消除高位的1位，因为高位的影响比低位更大。

解题思路分为几个步骤：

  1. 位枚举策略：从最高位开始，逐位检查是否能通过k次操作将该位消除。使用mask变量累积我们想要消除的位。

  2. 可行性检查：对于当前的mask，检查是否存在一个操作序列能使最终结果与mask的按位与为0。

    • 如果所有元素的按位与结果globalAnd与mask有公共位，说明无论如何操作都无法消除这些位
    • 否则，计算消除这些位所需的最小操作次数

  3. 操作次数计算：

    • 从左到右遍历数组，如果当前元素与mask有公共位，就对该位置执行操作
    • 通过连续的按位与操作模拟实际的消除过程
    • 如果最终所有元素的按位与不为0，还需要额外一次操作

  4. 贪心选择：如果所需操作次数不超过k，则将当前位加入mask；否则跳过该位。

这种方法确保我们总是优先消除对结果影响最大的高位，从而得到最小的按位或结果。

代码实现

class Solution {
public:
    int minOrAfterOperations(vector<int>& nums, int k) {
        int mask = 0;
        
        for (int bit = 29; bit >= 0; bit--) {
            int newMask = mask | (1 << bit);
            
            int globalAnd = 0;
            for (int num : nums) {
                globalAnd |= num;
            }
            
            if ((globalAnd & newMask) != 0) {
                vector<int> temp = nums;
                int operations = 0;
                
                for (int i = 0; i < temp.size() - 1; ) {
                    if ((temp[i] & newMask) != 0) {
                        temp[i] = temp[i] & temp[i + 1];
                        temp.erase(temp.begin() + i + 1);
                        operations++;
                    } else {
                        i++;
                    }
                }
                
                globalAnd = 0;
                for (int num : temp) {
                    globalAnd |= num;
                }
                if ((globalAnd & newMask) != 0) {
                    operations++;
                }
                
                if (operations <= k) {
                    mask = newMask;
                }
            } else {
                mask = newMask;
            }
        }
        
        vector<int> temp = nums;
        for (int i = 0; i < temp.size() - 1; ) {
            if ((temp[i] & mask) != 0) {
                temp[i] = temp[i] & temp[i + 1];
                temp.erase(temp.begin() + i + 1);
            } else {
                i++;
            }
        }
        
        int result = 0;
        for (int num : temp) {
            result |= num;
        }
        
        return result;
    }
};

class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        mask = 0
        
        for bit in range(29, -1, -1):
            new_mask = mask | (1 << bit)
            
            global_and = 0
            for num in nums:
                global_and |= num
            
            if (global_and & new_mask) != 0:
                temp = nums[:]
                operations = 0
                
                i = 0
                while i < len(temp) - 1:
                    if (temp[i] & new_mask) != 0:
                        temp[i] = temp[i] & temp[i + 1]
                        temp.pop(i + 1)
                        operations += 1
                    else:
                        i += 1
                
                global_and = 0
                for num in temp:
                    global_and |= num
                if (global_and & new_mask) != 0:
                    operations += 1
                
                if operations <= k:
                    mask = new_mask
            else:
                mask = new_mask
        
        temp = nums[:]
        i = 0
        while i < len(temp) - 1:
            if (temp[i] & mask) != 0:
                temp[i] = temp[i] & temp[i + 1]
                temp.pop(i + 1)
            else:
                i += 1
        
        result = 0
        for num in temp:
            result |= num
        
        return result

public class Solution {
    public int MinOrAfterOperations(int[] nums, int k) {
        int mask = 0;
        
        for (int bit = 29; bit >= 0; bit--) {
            int newMask = mask | (1 << bit);
            
            int globalAnd = 0;
            foreach (int num in nums) {
                globalAnd |= num;
            }
            
            if ((globalAnd & newMask) != 0) {
                var temp = new List<int>(nums);
                int operations = 0;
                
                for (int i = 0; i < temp.Count - 1; ) {
                    if ((temp[i] & newMask) != 0) {
                        temp[i] = temp[i] & temp[i + 1];
                        temp.RemoveAt(i + 1);
                        operations++;
                    } else {
                        i++;
                    }
                }
                
                globalAnd = 0;
                foreach (int num in temp) {
                    globalAnd |= num;
                }
                if ((globalAnd & newMask) != 0) {
                    operations++;
                }
                
                if (operations <= k) {
                    mask = newMask;
                }
            } else {
                mask = newMask;
            }
        }
        
        var result_temp = new List<int>(nums);
        for (int i = 0; i < result_temp.Count - 1; ) {
            if ((result_temp[i] & mask) != 0) {
                result_temp[i] = result_temp[i] & result_temp[i + 1];
                result_temp.RemoveAt(i + 1);
            } else {
                i++;
            }
        }
        
        int result = 0;
        foreach (int num in result_temp) {
            result |= num;
        }
        
        return result;
    }
}

var minOrAfterOperations = function(nums, k) {
    let mask = 0;
    
    for (let bit = 29; bit >= 0; bit--) {
        let newMask = mask | (1 << bit);
        
        let globalAnd = 0;
        for (let num of nums) {
            globalAnd |= num;
        }
        
        if ((globalAnd & newMask) !== 0) {
            let temp = [...nums];
            let operations = 0;
            
            for (let i = 0; i < temp.length - 1; ) {
                if ((temp[i] & newMask) !== 0) {
                    temp[i] = temp[i] & temp[i + 1];
                    temp.splice(i + 1, 1);
                    operations++;
                } else {
                    i++;
                }
            }
            
            globalAnd = 0;
            for (let num of temp) {
                globalAnd |= num;
            }
            if ((globalAnd & newMask) !== 0) {
                operations++;
            }
            
            if (operations <= k) {
                mask = newMask;
            }
        } else {
            mask = newMask;
        }
    }
    
    let temp = [...nums];
    for (let i = 0; i < temp.length - 1; ) {
        if ((temp[i] & mask) !== 0) {
            temp[i] = temp[i] & temp[i + 1];
            temp.splice(i + 1, 1);
        } else {
            i++;
        }
    }
    
    let result = 0;
    for (let num of temp) {
        result |= num;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(30 × n²)，其中n为数组长度。对每个位进行30次检查，每次检查需要O(n²)时间模拟操作过程
空间复杂度O(n)，需要额外空间存储临时数组进行模拟

相关题目