前置题目

208. 实现 Trie (前缀树)

前缀树的介绍：参考

代码实现：

C++

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
        memset(next,0,sizeof(next));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node = this;
        for(char c:word){
            if(node->next[c-'a']==NULL){
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node = this;
        for(char c:word){
            node = node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return node->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node = this;
        for(char c:prefix){
            node = node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return true;
    }
};
//https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/
/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

421. 数组中两个数的最大异或值

参考

C++

struct Trie{
    //左子树指向表示0的子节点
    Trie* left = nullptr;
    //右子树指向表示1的子节点
    Trie* right = nullptr;
    Trie(){}
};

class Solution {
private:
    //字典树的根节点
    Trie* root = new Trie();
    //最高位的二进制编号为30
    static constexpr int HIGH_BIT = 30;

public:
    void add(int num){
        Trie* cur = root;
        for(int k = HIGH_BIT;k>=0;--k){
            int bit = (num>>k)&1;
            if(bit==0){
                if(!cur->left){
                    cur->left = new Trie();
                }
                cur = cur->left;
            }else{
                if(!cur->right){
                    cur->right = new  Trie();
                }
                cur = cur->right;
            }
        }
    }

    int check(int num){
        Trie* cur = root;
        int x = 0;
        for(int k = HIGH_BIT;k>=0;--k){
            int bit = (num>>k)&1;
            if(bit==0){
                //a_i的第k个二进制位为0，应当往表示1的子节点right走
                if(cur->right){//cur->right存在
                    cur = cur->right;
                    x = x*2 + 1;
                }else{
                    cur = cur->left;
                    //x*2表示左移
                    x = x*2;
                }
            }else{
                //a_i的第k个二进制位为1，应当往表示0的子节点left走
                if(cur->left){
                    cur = cur->left;
                    x = x*2 + 1;//1和0异或的结果为1
                }else{
                    cur = cur->right;
                    x = x*2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for(int i = 1;i<n;++i){
            //将nums[i-1]放入字典树，此时nums[0...i-1]都在字典树中
            add(nums[i-1]);
            //将nums[i]看作ai,找出最大的x更新答案
            x = max(x,check(nums[i]));
        }
        return x;
    }
};
//https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/shu-zu-zhong-liang-ge-shu-de-zui-da-yi-h-n9m9/