Leetcode 421

给定一个数组，求两个数异或后的值最大是多少

sol: 注意到异或一个性质, 如果a^b=c那么 b^c=a

详细的题解看这里， https://kingsfish.github.io/2017/12/15/Leetcode-421-Maximum-XOR-of-Two-Numbers-in-an-Array/

写的非常好

    public int findMaximumXOR(int[] nums) {int res = 0;for (int i = 30; i >= 0; i--) {int mask = 1 << i;res |= mask;Set set = new HashSet<>();for (int x : nums) set.add(x & res);boolean f = false;for (int x : set) {if (set.contains(x ^ res)) {//该位能取到1f = true;break;}}//该位取不到1,置为0if (!f) res ^= mask;}return res;}

这题还有一种做法，是构建一颗数，然后每个数都沿着和当前位相反的方向走(异或才会大),取最大值.

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91059/java-on-solution-using-trie

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！