Maximum XOR of Two Numbers in an Array

leap_frog 發布于2019-08-14 17:18 / 2210人閱讀

摘要：把所有放進，之后對每一個從最高位找是否存在和當前不同的。把多帶帶寫一個函數，結果了，所以放一起了。。如果有就把放進去，當前結果累計到下一個循環。把所有放進里面找出中是否有兩個數后等于的結果有就更新第二步根據

標題文字

鏈接：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()示例代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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