1. 解题思路
这一题思路上来说我们就是逐位进行考虑。
因此,这里我们主要需要考虑的就是第二种情况,也就是对于这些位上的01分配问题,而这个不难证明,假设其他位上有结论
>
2. 代码实现
class Solution:
def maximumXorProduct(self, a: int, b: int, n: int) -> int:
MOD = 10**9 + 7
def num2digits(num):
digits = [0 for i in range(50)]
idx = 0
while num != 0:
digits[idx] = num % 2
num = num // 2
idx += 1
return digits
def digits2num(digits):
flag = 1
ans = 0
for d in digits:
ans += flag * d
flag = flag * 2 % MOD
return ans % MOD
def convert(digits_a, digits_b):
status = 0
for idx in range(49, -1, -1):
if idx >= n:
if digits_a[idx] > digits_b[idx]:
if status == 0:
status = 1
elif digits_a[idx] < digits_b[idx]:
if status == 0:
status = 2
continue
if digits_a[idx] == 0 and digits_b[idx] == 0:
digits_a[idx] = 1
digits_b[idx] = 1
elif digits_a[idx] == 1 and digits_b[idx] == 1:
digits_a[idx] = 1
digits_b[idx] = 1
elif digits_a[idx] == 0 and digits_b[idx] == 1:
if status == 0:
status = 2
elif status == 2:
digits_a[idx] = 1
digits_b[idx] = 0
else:
if status == 0:
status = 1
elif status == 1:
digits_a[idx] = 0
digits_b[idx] = 1
return
digits_a = num2digits(a)
digits_b = num2digits(b)
convert(digits_a, digits_b)
na = digits2num(digits_a)
nb = digits2num(digits_b)
return na * nb % MOD
3. 代码优化:
看了一下大佬们的提交结果,思路也大差不差,不过实现上就比我优雅很多了,给一个大佬的实现如下,膜拜一下。
class Solution:
def maximumXorProduct(self, a: int, b: int, n: int) -> int:
for i in range(n):
if (a & (1 << i)) == 0 and (b & (1 << i)) == 0:
a += 1 << i
b += 1 << i
for i in range(n):
if a > b and (a & (1 << i)) != 0 and (b & (1 << i)) == 0 and (a - (1 << i)) * (b + (1 << i)) > a * b:
a -= 1 << i
b += 1 << i
elif a < b and (a & (1 << i)) == 0 and (b & (1 << i)) != 0 and (a + (1 << i)) * (b - (1 << i)) > a * b:
a += 1 << i
b -= 1 << i
return a * b % int(1e9 + 7)
原文地址:https://blog.csdn.net/codename_cys/article/details/134631972
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12567.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。