Swift solution - Trie, Bit Manipulation


  • 0
    public class Trie {
        var children: [Trie?]
        
        public init() {
            self.children = [Trie?](repeatElement(nil, count: 2))
        }
    }
    
    class Solution {
        func findMaximumXOR(_ nums: [Int]) -> Int {
            if nums.count == 0 {
                return 0
            }
            
            let root = Trie()
            var result = Int.min
            
            for num in nums {
                var curNode = root
                for i in stride(from: 31, through: 0, by: -1) {
                    let curBit = (num >> i) & 1
                    if curNode.children[curBit] == nil {
                        curNode.children[curBit] = Trie421()
                    }
                    curNode = curNode.children[curBit]!
                }
            }
            
            for num in nums {
                var curNode = root
                var curSum = 0
                for i in stride(from: 31, through: 0, by: -1) {
                    let curBit = (num >> i) & 1
                    if curNode.children[curBit ^ 1] != nil {
                        curSum += (1 << i)
                        curNode = curNode.children[curBit ^ 1]!
                    } else {
                        curNode = curNode.children[curBit]!
                    }
                }
                result = max(curSum, result)
            }
            
            return result
        }
    
        func findMaximumXOR_BitManipulation(_ nums: [Int]) -> Int {
            var result = 0
            var mask = 0
            
            for i in stride(from: 31, through: 0, by: -1) {
                mask |= (1 << i)
                let tmp = result | (1 << i)
                var set = Set<Int>()
                for num in nums {
                    set.insert(num & mask)
                }
                for prefix in set {
                    if set.contains(tmp ^ prefix) {
                        result = tmp
                        break
                    }
                }
            }
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.