vue快速建站,网站开发法律,佛山顺德网站建设公司,河间网站建设公司Leetcode 2939. Maximum Xor Product 1. 解题思路2. 代码实现3. 代码优化#xff1a; 题目链接#xff1a;2939. Maximum Xor Product
1. 解题思路
这一题思路上来说我们就是逐位进行考虑。
对于xor操作#xff0c;显然我们只有以下两种情况#xff1a;
00或者11…Leetcode 2939. Maximum Xor Product 1. 解题思路2. 代码实现3. 代码优化 题目链接2939. Maximum Xor Product
1. 解题思路
这一题思路上来说我们就是逐位进行考虑。
对于xor操作显然我们只有以下两种情况
00或者11此时我们总可以令两者都变成11此时获得的乘积一定最大01或者10此时我们变换的结果也是01或者10但两者的乘积变化就会有所区别。
因此这里我们主要需要考虑的就是第二种情况也就是对于这些位上的01分配问题而这个不难证明假设其他位上有结论 a b ab ab那么总是将1分配到b上面可以使得结果更大。
故而我们只需要基于这个思路进行代码实现就行了。
2. 代码实现
给出python代码实现如下
class Solution:def maximumXorProduct(self, a: int, b: int, n: int) - int:MOD 10**9 7def num2digits(num):digits [0 for i in range(50)]idx 0while num ! 0:digits[idx] num % 2num num // 2idx 1return digitsdef digits2num(digits):flag 1ans 0for d in digits:ans flag * dflag flag * 2 % MODreturn ans % MODdef convert(digits_a, digits_b):status 0for idx in range(49, -1, -1):if idx n:if digits_a[idx] digits_b[idx]:if status 0:status 1elif digits_a[idx] digits_b[idx]:if status 0:status 2continueif digits_a[idx] 0 and digits_b[idx] 0:digits_a[idx] 1digits_b[idx] 1elif digits_a[idx] 1 and digits_b[idx] 1:digits_a[idx] 1digits_b[idx] 1elif digits_a[idx] 0 and digits_b[idx] 1:if status 0:status 2elif status 2:digits_a[idx] 1digits_b[idx] 0else:if status 0:status 1elif status 1:digits_a[idx] 0digits_b[idx] 1returndigits_a num2digits(a)digits_b num2digits(b)convert(digits_a, digits_b)na digits2num(digits_a)nb digits2num(digits_b)return na * nb % MOD 提交代码评测得到耗时69ms占用内存16.3MB。
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 ib 1 ifor 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 ib 1 ielif a b and (a (1 i)) 0 and (b (1 i)) ! 0 and (a (1 i)) * (b - (1 i)) a * b:a 1 ib - 1 ireturn a * b % int(1e9 7)
