leetcode每日一题：最大或值
题目
2680. 最大或值
给你一个下标从 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 <= 105 -
1 <= nums[i] <= 109 -
1 <= k <= 15
思路
考虑了挺久，看到方法最后的返回值是long，才反应过来。本题其实有个隐含的条件没有说，就是选择1个数乘以2之后，是可以超出int范围的。有了这个条件之后，就豁然开朗了。那要让最后的或值最大，肯定要把这k次操作用在同一个数字上。因为每次乘以2的操作，相当于二进制数的左移1位，选择同一个数左移，才能把最高的1移动到尽量靠左，即更加高位的位置，让整体数值最大。
接下来就是在遍历的过程中，如何快速计算。对于每个数，我们要计算这个数左移k位，跟剩余其他数值的或值。为了避免重复计算，我们定义2个数组prefix[]和suffix[]，prefix[i]代表nums[0, i-1]的或值，suffix[i]代表nums[i+1, n-1]的或值。可以运用类似前缀和的方法，预先计算好这2个数组，然后再遍历nums计算最大或值。这里有一个小技巧，对prefix[]的计算，由于是从前往后遍历的，可以跟nums的遍历放在同一个for循环中，这样可以减少一次遍历，虽然时间复杂度不变，不过也可以节省一些执行时间。
图解
代码
public long maximumOr(int[] nums, int k) {
int n = nums.length;
// 后缀 or 结果
int[] suffix = new int[n];
for (int i = n - 1; i >= 1; i--) {
suffix[i-1] = suffix[i] | nums[i];
}
long ans = 0;
long prefix = 0;
for (int i = 0; i < n; i++) {
ans = Math.max(ans, prefix | ((long) nums[i] << k) | suffix[i]);
prefix |= (long) nums[i];
}
return ans;
}
优化
上述方法中，开了2个长度为n的数组prefix[]和suffix[]，我们想办法优化。最直接可以想到的是，我们对nums所有的值先做1次or计算，得到orResult，然后在遍历到某个值num的时候，通过异或预算，去除掉这个num的影响，这样就获的了去除当前num，剩余所有值的或结果。
但是这样会存在一个问题：对于num的二进制表示中所有为1的位，异或运算后都变成了0，如果这1位其他数是有1的，那么就多去除了。所以，我们还需要计算一个值fixed，代表在这1位，至少存在2个数的二进制表示为1，那么无论结果选择对那个num进行左移，这1位固定为1，我们在异或计算后，再次或运算fixed，就可以得到真正的，去除当前num后，剩余数值的或值。
优化后代码
public long maximumOr(int[] nums, int k) {
long orResult = 0;
// 如果多个数值在某1位是1，那么无论这个数是否做位移，or的结果这1位一定是1
long fixed = 0;
for (int num : nums) {
fixed |= orResult & num;
orResult |= num;
}
// 遍历的时候，通过 ^num 把这一位的数值排除掉，同时 |fixed 避免多排除的影响
long ans = 0;
for (int num : nums) {
ans = Math.max(ans, (orResult ^ num) | fixed | ((long)num<<k));
}
return ans;
}
耗时
