LeetCode 2680.最大或值：位运算

【LetMeFly】2680.最大或值：位运算

力扣题目链接：https://leetcode.cn/problems/maximum-or/

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 15

很不错的一道题！位运算的与或异或都考察了。

解题方法一：前缀和

首先需要发现并理解的是：一定要每次都将“二进制下位数最长的那个数乘2”。

假如a二进制下是3位，b二进制下是2位，那么将b乘以2后和a或运算还是3位，一定不如将a乘以2变成2位大。

二进制下长度最长的数有多个，如何选择呢？

无所谓，每个都试试呗。我们只需要逮着一个数一直乘以2共k次，判断所有选择中结果最大的那个就好了。

这一听不是 $O(n^2)$ 吗，如何优化？

使用一个前缀和 $p re f i x [i]$ 代表从下标 $0$ 或到下标 $i$ 这个元素的结果，“后缀和” $s u ff i x [i]$ 代表从最后一个元素或到下标 $i$ 的结果。

那么，如果将 $n u m s [i]$ 乘以 $k$ 次 $2$ 的话，最终的或结果就是 $1]\ |\ nums[i] << k\ |\ suffix[i + 1]$ 。

所有的这些结果中，最大的那个即为答案。

时间复杂度 $O (l e n (n u m s))$
空间复杂度 $O (l e n (n u m s))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-03-21 15:09:09* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-21 15:17:06*/
#ifdef _WIN32
#include "_[1,2]toVector.h"
#endiftypedef long long ll;class Solution {
public:ll maximumOr(vector<int>& nums, int k) {vector<int> suffix(nums.size() + 1);for (int i = nums.size() - 1; i >= 0; i--) {suffix[i] = suffix[i + 1] | nums[i];}ll ans = 0;int prefix = 0;for (int i = 0; i < nums.size(); i++) {ans = max(ans, (ll)(nums[i]) << k | prefix | suffix[i + 1]);prefix |= nums[i];}return ans;}
};

解题方法二：位运算

方法一空间复杂度为 $O (n)$ ，可否使用位运算优化？例如我单独将 $n u m s [i]$ 拎出来左移 $k$ 次的话，如何在 $O (1)$ 空间下快速判断出剩下所有元素的或值为多少？

假设数组中所有元素或运算的结果为 $a llO r$ ：

对于 $n u m s [i]$ 二进制下的某个 $1$ ，如果其他元素中这一位也有出现过 $1$ ，那么拎出来 $n u m s [i]$ 后剩下元素这一位的或结果和 $a llO r$ 相同

对于 $n u m s [i]$ 二进制下的某个 $1$ ，如果其他元素中这一位没有出现过 $1$ ，那么拎出来 $n u m s [i]$ 后剩下元素这一位的或结果和 $a llO r$ 不同

也就是说，我们只需要统计一下哪一位 $1$ 出现过最少两次（ $a ll 1$ 为 $1$ 的位代表至少有两个数这一位为 $1$ ），如果 $n u m s [i]$ 这一位为 $1$ 的话，依据 $a ll 1$ 的这一位是否为 $1$ ，就能判断出其他元素中是否存在这一位为 $1$ 的情况，就能得知除 $n u m s [i]$ 外其他元素这一位或运算的结果是否为 $1$ 了。

最后就剩下了一个问题：如何求出 $a ll 1$ ？

同样使用前缀和的思路， $p re f i x$ 代表从第一个元素到当前元素的上一个元素为止的或结果。

如果那么 $prefix\ \&\ nums[i]$ 的某一位为 $1$ 的话，就代表 $n u m s [i]$ 和前面的数中的某些数这一位都为 $1$ ，也就是说这一位至少出现了两次 $1$

因此将 $a ll 1$ 或上 $prefix\ \&\ nums[i]$ 即可。

这样，遍历到 $n u m s [i]$ 时， $allOr\ \^\ nums[i]\ |\ all1$ 即为所有元素除去 $n u m s [i]$ 后的或结果。

时间复杂度 $O (l e n (n u m s))$
空间复杂度 $O (1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-03-21 15:29:27* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-21 15:32:32* @Descriptions: Fake Time* @Descriptions: AC,100.00%,90.30%*/
typedef long long ll;class Solution {
public:ll maximumOr(vector<int>& nums, int k) {int allOr = 0, all1 = 0;for (int t : nums) {all1 |= allOr & t;allOr |= t;}ll ans = 0;for (int t : nums) {ans = max(ans, allOr ^ t | all1 | (ll)(t) << k);}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-03-21 15:21:19
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-21 15:27:03
'''
from typing import Listclass Solution:def maximumOr(self, nums: List[int], k: int) -> int:allOr = all1 = 0for t in nums:all1 |= t & allOrallOr |= tans = 0for t in nums:ans = max(ans, t ^ allOr | all1 | t << k)return ans

Java

/** @Author: LetMeFly* @Date: 2025-03-21 15:32:20* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-21 15:34:12*/
class Solution {public long maximumOr(int[] nums, int k) {int allOr = 0, all1 = 0;for (int t : nums) {all1 |= t & allOr;allOr |= t;}long ans = 0;for (int t : nums) {ans = Math.max(ans, allOr ^ t | all1 | (long)t << k);}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-03-21 15:34:47* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-21 16:32:51* @Description: Go int和int64的位运算似乎几乎一点都不会自动转换类型*/
package mainfunc maximumOr(nums []int, k int) (ans int64) {allOr, all1 := 0, 0for _, t := range nums {all1 |= allOr & tallOr |= t}for _, t := range nums {ans = max(ans, int64(allOr) ^ int64(t) | int64(all1) | int64(t) << k)}return
}