Leetcode 3670. Maximum Product of Two Integers With No Common Bits

• Leetcode 3670. Maximum Product of Two Integers With No Common Bits
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3670. Maximum Product of Two Integers With No Common Bits

1. 解题思路

这一题我的思路挺暴力的，就是先构造一个trie树，然后搜索对任意$n$的最大的补数，然后考察所有结果的最大值。

然后直接的实现出现了超时的问题，因此我做了不少剪枝修补，感觉不是最好的实现方法，有兴趣的读者建议还是再想想有没有什么更好的解法吧……

2. 代码实现

给出python代码实现如下：

DIGIT_NUM = 20class Trie:def __init__(self):self.trie = {}def add(self, num):word = bin(num)[2:].rjust(DIGIT_NUM, "0")trie = self.triefor c in word:trie = trie.setdefault(c, {})trie["eos"] = num@lru_cache(None)def find(self, num):word = bin(num)[2:].rjust(DIGIT_NUM, "0")trie = self.triedef dfs(idx, trie):if idx == DIGIT_NUM:return trie.get("eos", 0)if trie == {}:return 0if word[idx] == "1":return dfs(idx+1, trie["0"]) if "0" in trie else 0else:return max(dfs(idx+1, trie.get("0", {})), dfs(idx+1, trie.get("1", {})))return dfs(0, trie)@lru_cache(None)
def get_rev(num):num = bin(num)[2:]digits = [1-int(x) for x in num]ans = 0for d in digits:ans = 2*ans+dreturn ansclass Solution:def maxProduct(self, nums: List[int]) -> int:snums = set(nums)nums = list(snums)trie = Trie()for num in nums:trie.add(num)nums = sorted(nums, reverse=True)ans = 0for num in nums:rev = get_rev(num)if num * num <= ans:breakif get_rev(num) in snums:ans = max(ans, num * get_rev(num))continueans = max(ans, num * trie.find(num))return ans

提交代码评测得到：耗时16912ms，占用内存319.43MB。