【LeetCode每日一题 】Trie树模板+贪心+两数之和+Set核心题目 三种方法(421)
【LeetCode每日一题 】Trie树模板+贪心+两数之和+Set核心题目 三种方法(421)
公众号guangcity
发布于 2021-05-31 10:38:39
发布于 2021-05-31 10:38:39
文章被收录于专栏：光城(guangcity)
今日题目非常重要，考察了贪心、Trie树、Set、两数之和。在探讨本题同时，给出set解法与trie树模板以及剪枝策略。
题目：
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
题解：
我们先来看一下贪心+两数之后+Set的思想。
我们知道异或公式：
a ^ b = c 推出 a ^ c = b
而要想让两个数的异或值最大，那便是从最高位开始算，如果存在两个数当前位异或结果为1，那么将可以获得最大异或值。
而从最高位往最低为计算时：我们可以得到下面计算：
1 0 0 0 0 mask
---------------
0 0 0 1 1 3
0 1 0 1 0 10
0 0 1 0 1 5
1 1 0 0 1 25
0 0 0 1 0 2
0 1 0 0 0 8
---------------
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
