楼主:
Meaverzt (Meaverzt)
2025-01-15 14:16:00题目:
有两个数字num1跟num2
我们要找出符合两个条件的一个x
1.x 的binary representation 中的1要跟num2一样多
2.x跟num1 xor后的值要最小
思路:
为了让xor后的值高位数的1越少越好
在高位数的num1是1 x就要是1 是0 x就要是0
所以一开始先数num2里面有几个1设做num
从num1的高位遍历到低位
在num>0的情况下只要遇到1答案的这位就填1
如果全部的1都填完了 num还是>0
那就从低位到高位再遍历一次num1
遇到0的时候填1保持xor后的值最小直到num=0
最后把结果转回整数就是答案了
Code:
class Solution(object):
def minimizeXor(self, num1, num2):
num1,num2=bin(num1)[2:],bin(num2)[2:]
if len(num1)<len(num2):
num1=(len(num2)-len(num1))*'0'+num1
ans=['0' for i in num1]
num=0
for i in num2:
if i=='1':
num+=1
for i in range(len(num1)):
if num1[i]=='1' and num>0:
num-=1
ans[i]='1'
for i in range(len(num1)-1,-1,-1):
if num1[i]=='0' and num>0:
num-=1
ans[i]='1'
return int(''.join(ans),2)
位元运算太难了
只想的出用字串的
肥肥就这样了