给你一个下标从 0 开始的整数数组 nums
和一个整数 k
。
一次操作中,你可以选择 nums
中满足 0 <= i < nums.length - 1
的一个下标 i
,并将 nums[i]
和 nums[i + 1]
替换为数字 nums[i] & nums[i + 1]
,其中 &
表示按位 AND
操作。
请你返回 至多 k
次操作以内,使 nums
中所有剩余元素按位 OR
结果的 最小值 。
示例 1:
```txt
输入:nums = [3,5,3,2,7], k = 2
输出:3
解释:执行以下操作:
将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ,得到 nums 为 [1,3,2,7] 。
将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ,得到 nums 为 [1,3,2] 。
最终数组的按位或值为 3 。
3 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
```
示例 2:
```txt
输入:nums = [7,3,15,14,2,8], k = 4
输出:2
解释:执行以下操作:
将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ,得到 nums 为 [3,15,14,2,8] 。
将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ,得到 nums 为 [3,14,2,8] 。
将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ,得到 nums 为 [2,2,8] 。
将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ,得到 nums 为 [2,0] 。
最终数组的按位或值为 2 。
2 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
```
示例 3:
```txt
输入:nums = [10,7,10,3,9,14,9,4], k = 1
输出:15
解释:不执行任何操作,nums 的按位或值为 15 。
15 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
```
提示:
1 <= nums.length <= 10^5
0 <= nums[i] < 2^30
0 <= k < nums.length
给定操作次数内使剩余元素的或值最小
题目
给你一个下标从 0 开始的整数数组 nums
和一个整数 k
。
一次操作中,你可以选择 nums
中满足 0 <= i < nums.length - 1
的一个下标 i
,并将 nums[i]
和 nums[i + 1]
替换为数字 nums[i] & nums[i + 1]
,其中 &
表示按位 AND
操作。
请你返回 至多 k
次操作以内,使 nums
中所有剩余元素按位 OR
结果的 最小值 。
示例 1:
1 | 输入:nums = [3,5,3,2,7], k = 2 |
示例 2:
1 | 输入:nums = [7,3,15,14,2,8], k = 4 |
示例 3:
1 | 输入:nums = [10,7,10,3,9,14,9,4], k = 1 |
提示:
-
1 <= nums.length <= 10^5
-
0 <= nums[i] < 2^30
0 <= k < nums.length
题解
方法一:
思路
初始化答案为ans=(1<<30)-1
,三十位二进制全为1。
从高位起尝试置为0,当前构造的ans检测是否可行,
每次通过贪心的方式检测,当一段连续的区间内的数与和中,某位为1则对应的ans的位不应该为0,否则这段区间没有满足。一旦满足了一段区间则可以减少一次操作。最后操作次数不大于k当前位构造0是合法的。
代码
1 | class Solution { |