本文介绍: Leetcode 2939. Maximum Xor Product

1. 解题思路

这一题思路上来说我们就是逐位进行考虑。

对于xor操作,显然我们只有以下两种情况:

  1. 00或者11:此时我们可以令两者都变成11,此时获得的乘积一定最大
  2. 01或者10:此时我们变换结果也是01或者10,但两者的乘积变化就会有所区别

因此,这里我们主要需要考虑的就是第二种情况,也就是对于这些位上的01分配问题,而这个不难证明,假设其他位上有结论

a

>

b

a>b

a>b,那么总是将1分配到b上面可以使得结果更大。

故而,我们需要基于这个思路进行代码实现就行了。

2. 代码实现

给出python代码实现如下:

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          

提交代码评测得到:耗时69ms占用内存16.3MB。

3. 代码优化

看了一下大佬们的提交结果,思路也大差不差,不过实现上就比我优雅很多了,给一个大佬的实现如下,膜拜一下。

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int: 
        for i in range(n):
            if (a &amp; (1 << i)) == 0 and (b &amp; (1 << i)) == 0:
                a += 1 << i
                b += 1 << i
        for i in range(n):
            if a > b and (a &amp; (1 << i)) != 0 and (b &amp; (1 << i)) == 0 and (a - (1 << i)) * (b + (1 << i)) > a * b:
                a -= 1 << i
                b += 1 << i
            elif a < b and (a &amp; (1 << i)) == 0 and (b &amp; (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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注