今日题目非常重要,考察了贪心、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
---------------