Trie树

leetcode208.实现Trie

1. 思路

Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。
其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

2. 代码

public class Trie{
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public void insert(String s){
        TrieNode p = root;
        for(char c:s.toCharArray()){
            int index = c-'a';
            if(p.children[index]==null){
                p.children[index] = new TrieNode();
            }
           p = p.children[index];
        }
        p.end = true;
    }
    public boolean search(String s){
        TrieNode p = root;
        for(char c:s.toCharArray()){
            int index = c-'a';
            if(p.children[index]==null){
                return false;
            }
            p = p.children[index];
        }
        return p.end;
    }
    public boolean startsWith(String s){
        TrieNode p = root;
        for(char c:s.toCharArray()){
            int index = c-'a';
            if(p.children[index]==null){
                return false;
            }
            p = p.children[index];
        }
        return true;
    }
}

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

1. 思路

要求得数组nums 中的「最大异或结果」，假定 nums[i] 与 nums[j] 异或可以取得最终结果。由于异或计算「每位相互独立」（又称为不进位加法），同时具有「相同值异或结果为 0，不同值异或结果为 1」的特性。
因此对于 nums[j] 而言，可以从其二进制表示中的最高位开始往低位找，尽量让每一位的异或结果为 1，这样找到的 nums[i] 与 nums[j] 的异或结果才是最大的。
具体的，我们需要先将 nums 中下标范围为 [0, j]的数（二进制表示）加入Trie 中，然后每次贪心的匹配每一位（优先匹配与之不同的二进制位）。

2. 代码

class Solution {
    class Node {
        Node[] ns = new Node[2];
    }
    Node root = new Node();
    void add(int x) {
        Node p = root;i
        for (int i = 31; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (p.ns[u] == null) p.ns[u] = new Node();
            p = p.ns[u];
        }
    }
    int getVal(int x) {
        int ans = 0;
        Node p = root;
        for (int i = 31; i >= 0; i--) {
            int a = (x >> i) & 1, b = 1 - a;
            if (p.ns[b] != null) {
                ans |= (b << i);
                p = p.ns[b];
            } else {
                ans |= (a << i);
                p = p.ns[a];
            }
        }
        return ans;
    }
    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        for (int i : nums) {
            add(i);
            int j = getVal(i);
            ans = Math.max(ans, i ^ j);
        }
        return ans;
    }
}

leetcode1707.与数组中元素中的最大异或值

1. 思路

具体的，我们可以按照下面的逻辑进行处理：

1. 对 nums 进行「从小到大」进行排序，对 queries 的第二维进行「从小到大」排序（排序前先将询问原本的下标映射关系存下来）。
2. 按照排序顺序处理所有的 queries[i]：
   • 在回答每个询问前，将小于等于 queries[i][1] 的数值存入 TrieTrie。由于我们已经事先对 nums 进行排序，因此这个过程只需要维护一个在 nums 上有往右移动的指针即可。
   • 然后利用贪心思路，查询每个 queries[i][0] 所能找到的最大值是多少，计算异或和（此过程与 421. 数组中两个数的最大异或值 一致）。
   • 找到当前询问在原询问序列的下标，将答案存入。

     2. 代码

     ```java import java.util.Arrays; import java.util.HashMap;

public class MaximizeXor { class Node{ Node[] child = new Node[2]; } Node root = new Node(); void add(int x){ Node p = root; for(int i=31;i>=0;i—){ int u=(x>>i)&1; if(p.child[u]==null) p.child[u] = new Node(); p = p.child[u]; } }

int getVal(int x){
    int ans = 0;
    Node p=root;
    for(int i=31;i>=0;i--){
        int a=(x>>i)&1,b=1-a;
        if(p.child[b]!=null){
            p=p.child[b];
            ans=ans|(b<<i);
        }else {
            p=p.child[a];
            ans=ans|(a<<i);
        }
    }
    return ans^x;
}
public int[] maximizeXor(int[] nums, int[][] queries) {
    int m=nums.length,n= queries.length;
    HashMap<int[],Integer> map = new HashMap<>();
    for(int i=0;i<n;i++){
        map.put(queries[i],i);
    }
    Arrays.sort(nums);
    Arrays.sort(queries,(a,b)->a[1]-b[1]);
    int[] ans = new int[n];
    int loc = 0;
    for(int[] q:queries){
        int x=q[0],limit=q[1];
        while (loc<m&&nums[loc]<=limit){
            add(nums[loc++]);
        }
        if(loc==0){
            ans[map.get(q)]=-1;
        }else {
            ans[map.get(q)] = getVal(x);
        }
    }
    return ans;
}

}

```