- Leetcode 3133. Minimum Array End
- 1. 解题思路
- 2. 代码实现
- 题目链接:3133. Minimum Array End
1. 解题思路
这一题由于要求所有的array当中所有的数字的与为目标值,因此目标值当中的1的位必须保证所有的数均为1,剩下的位置只需要保证有一个0即可,因此,我们只需要取 0 0 0到 n − 1 n-1 n−1,将其二进制位填充到0所在的位置上即可,不够的位置则在头部补0。
也就是是说,我们就是将 n − 1 n-1 n−1的二进制位顺序补到目标值所有为0的位置上即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def minEnd(self, n: int, x: int) -> int:
move = bin(n-1)[2:]
x = bin(x)[2:]
idx = len(x)-1
ans = []
for ch in move[::-1]:
while idx >= 0 and x[idx] == "1":
ans.insert(0, 1)
idx -= 1
ans.insert(0, int(ch))
if idx != -1:
idx -= 1
while idx >= 0:
ans.insert(0, int(x[idx]))
idx -= 1
ret = 0
for d in ans:
ret = ret * 2 + d
return ret
提交代码评测得到:耗时31ms,占用内存16.6MB。