- Leetcode 3315. Construct the Minimum Bitwise Array II
- 1. 解题思路
- 2. 代码实现
- 题目链接:3315. Construct the Minimum Bitwise Array II
1. 解题思路
这一题有点类似脑筋急转弯,想明白了就很简单,想不明白的话的话就比较麻烦了……
这道题本质上就是给出任意一个数n,然后找到一个最小的数i,使得i | (i+1) = n
。
显然n必须为奇数,否则不会有解,然后对于任意一个奇数,我们要看怎么找最小的i,这个事实上就是把这个数n用二进制表示出来,然后从后往前找到最后一个连续的1,将其变为0即可。
2. 代码实现
给出python代码实现如下:
class Solution:def minBitwiseArray(self, nums: List[int]) -> List[int]:def fn(num):if num == 2:return -1d = 1while num & d > 0:d = d << 1d = d >> 1return num - dreturn [fn(num) for num in nums]
提交代码评测得到:耗时57ms,占用内存16.5MB。