最大或值
难度:
标签:
题目描述
You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2.
Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times.
Note that a | b denotes the bitwise or between two integers a and b.
Example 1:
Input: nums = [12,9], k = 1 Output: 30 Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.
Example 2:
Input: nums = [8,1,2], k = 2 Output: 35 Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 15
代码结果
运行时间: 72 ms, 内存: 28.5 MB
/*
* Problem: Given an integer array nums and an integer k, you can choose a number and multiply it by 2 in each operation.
* You can perform at most k operations. Return the maximum value of nums[0] | nums[1] | ... | nums[n - 1].
* Example:
* Input: nums = [12, 9], k = 1
* Output: 30
* Explanation: By doubling the element at index 1, we get [12, 18]. The result of 12 | 18 is 30.
*/
import java.util.Arrays;
public class Solution {
public int maximizeOr(int[] nums, int k) {
return Arrays.stream(nums)
.map(num -> num << k)
.reduce(0, (a, b) -> a | b);
}
}
解释
方法:
该题解主要通过位运算的方法来尝试在进行最多k次数值翻倍的操作后，获取最大的按位或结果。首先，使用两个变量v和v2，其中v存储数组nums中所有元素的按位或结果，v2存储在某些位上至少有两个数都为1的情况的按位或结果。接着，如果v2与v相同，并且v加1后与自身进行按位与的结果为0（说明v是2的幂减一的形式），则直接返回最大数左移k位后与v进行按位或的结果。否则，对于每个数x，计算x左移k位后与其自身与v按位异或后的结果再与v2按位或的结果，并返回这些计算中的最大值。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解法中，变量`v`和`v2`的目的及其在算法中的作用是什么？
▷🦆
解法中提到的条件`v2 == v`和`(v + 1 & v) == 0`分别检查了什么？为什么这些检查后可以直接计算最终结果？
▷🦆
如何理解`v2 |= v & x`这一行代码？它是如何更新`v2`的值的？
▷🦆
为什么在计算最大按位或值时，会选择将最大数左移k位？这样做的优势在哪里？
▷