Maximum XOR of Two Numbers in an Array

leap_frog 发布于2019-08-14 17:18 / 2217人阅读

摘要：把所有放进，之后对每一个从最高位找是否存在和当前不同的。把多带带写一个函数，结果了，所以放一起了。。如果有就把放进去，当前结果累计到下一个循环。把所有放进里面找出中是否有两个数后等于的结果有就更新第二步根据

标题文字

链接：https://leetcode.com/problems...

可以用trie tree来做。把所有num放进tree，之后对每一个num从最高位找是否存在和当前bit不同的path。把build tree多带带写一个函数，结果TLE了，所以放一起了。。

public class Solution {
    public int findMaximumXOR(int[] nums) {
        /* trie tree: root is the largest bit
         * 32 bits
         */
        TrieNode root = new TrieNode();
        for(int num : nums) {
            TrieNode node = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if(node.children[bit] == null) node.children[bit] = new TrieNode();
                node = node.children[bit];
            }
        }
        
        int globalMax = Integer.MIN_VALUE;
        
        for(int num : nums) {
            int local = 0;
            TrieNode node = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if(node.children[bit ^ 1] != null) {
                    local += (1 << i);
                    node = node.children[bit ^ 1];
                }
                else node = node.children[bit];
            }
            globalMax = Math.max(globalMax, local);
        }
        return globalMax;
    }
    
    class TrieNode {
        TrieNode[] children = new TrieNode[2];
    }
    
}

看到discussion还有一种简单的方法，从最高位开始扫，每次在nums里面找有没有两个数XOR可以等于1。如果有就把1放进去，当前结果累计到下一个循环。用一个set存到第i位位置的数，然后通过XOR就能找到有没有可以匹配的数。

把所有num(31, i)放进set里面

找出set中是否有两个数XOR后等于i = 1的结果

有就更新globalMax

第二步根据 x ^ y = z, then x ^ z = y

public class Solution {
    public int findMaximumXOR(int[] nums) {
         int globalMax = 0, highestBits = 0;
         for(int i = 31; i >= 0; i--) {
             // 1000 -> 1100 -> 1110 -> 1111
             highestBits = highestBits | (1 << i);
             Set set = new HashSet();
             for(int num : nums) {
                 set.add(num & highestBits);
             }
             
             // find if current bit can be 1
             int addOne = globalMax | (1 << i);
             for(int num : set) {
                 if(set.contains(num ^ addOne)) {
                     globalMax = addOne;
                     break;
                 }
             }
         }
         return globalMax;
    }

}

GPU云服务器云服务器 in_array() in_array in_array()函数 in_array()示例代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66549.html

【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合条件的总数。双指针区间考虑边界，长度，为空，等。之后的范围用双指针和表示。若三个指针的数字之和为，加入结果数组。不要求，所以不用判断了。同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 评论0 收藏0
【7 kyu】Sum of two lowest positive integers

摘要：原题目题目有一个不少于四个元素的数组，计算其中两个最小值的和。对比我写的方法比较常规，中采用了的解构赋值和箭头函数原题目 Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty ...

fjcgreat 2019-08-21 16:49 评论0 收藏0
leetcode 167 Two Sum II - Input array is sorted

摘要：同时题目假设每组输入恰好只有一个答案，并且不能重复使用同一元素。理解这道题是可以用两层循环蛮力解决的，但是效率太低了。如果这两个元素和大于目标数组，指针左移如果小于，指针右移。如果等于，则返回这两个元素的位置记得用数组的数值加一解法题目详情 Given an array of integers that is already sorted in ascending order, fi...

Keagan 2019-08-15 13:44 评论0 收藏0
[LintCode] K-diff Pairs in an Array

Problem Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both nu...

Leck1e 2019-08-15 18:16 评论0 收藏0
【LC总结】图、拓扑排序 (Course Schedule I, II/Alien Dictiona

Course Schedule Problem There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, whi...

gaara 2019-08-14 15:54 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0