Trie练习

我会带着你远行 2022-12-30 13:51 87阅读 0赞

## LeetCode208. 实现 Trie (前缀树) ##

1.  题目描述  
    实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。  
    Trie trie = new Trie();  
    trie.insert(“apple”);  
    trie.search(“apple”); // 返回 true  
    trie.search(“app”); // 返回 false  
    trie.startsWith(“app”); // 返回 true  
    trie.insert(“app”);  
    trie.search(“app”); // 返回 true

*  说明:你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

1.  代码

class Trie {
        
    public:
        static const int N = 1000000, M = 26;
        int son[N][M];
        int idx;
        int cnt[N];
    
        /** Initialize your data structure here. */
        Trie() {
        
            idx = 0;
            memset(son, 0, sizeof(son));
            memset(cnt, 0, sizeof(cnt));
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
        
            int p = 0;
            for(int i = 0;i < word.size();i++)
            {
        
                int &s = son[p][word[i] - 'a'];
                if(!s) s = ++idx;
                p = s;
            }
            cnt[p]++;
            return;
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
        
            int p = 0;
            for(int i = 0;i < word.size();i++)
            {
        
                int &s = son[p][word[i] - 'a'];
                if(!s) return false;
                p = s;
            }
            return cnt[p] > 0;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
        
            int p = 0;
            for(int i = 0;i < prefix.size();++i)
            {
        
                int &s = son[p][prefix[i] - 'a'];
                if(!s) return false;
                p = s;
            }
            return true;
        }
    };
    
    /**
     * 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);
     */

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

1.  题目描述  
    给定一个非空数组，数组中元素为  a 0 , a 1 , a 2 , … , a n − 1 ， 其 中 0 ≤ a i < 2 31 a\_0, a\_1, a\_2, … , a\_\{n-1\}，其中 0 ≤ a\_i < 2^\{31\} a0,a1,a2,…,an−1，其中0≤ai<231找到 a i a\_i ai 和 a j a\_j aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。  
    你能在O(n)的时间解决这个问题吗？  
    **输入**  
    \[3, 10, 5, 25, 2, 8\]  
    **输出**  
    28
2.  代码

class Solution {
        
    public:
    
        static const int N = 3000000;
        int son[N][2], idx = 0;
    
        void insert(int num)
        {
        
            int p = 0;
            for(int i = 30; ~i; --i)
            {
        
                int x = num >> i & 1;
                int &s = son[p][x];
                if(!s) s = ++idx;
                p = s;
            }
            return;
        }
    
        int query(int num)
        {
        
            int res = 0;
            int p = 0;
            for(int i = 30; ~i;--i)
            {
        
                int x = num >> i & 1;
                if(son[p][!x])
                {
        
                    res <<= 1;
                    res |= !x;
                    p = son[p][!x];
                }
                else
                {
        
                    res <<= 1;
                    res |= x;
                    p = son[p][x];
                }
            }
            return res;
        }
    
        int findMaximumXOR(vector<int>& nums) {
        
    
            int res = 0;
            for(int i = 0;i < nums.size(); ++i) insert(nums[i]);
            
            for(int i = 0;i < nums.size(); ++i)
            {
        
                res = max(res, nums[i] ^ query(nums[i]));
            }
    
            return res;
        }
    };

## Acwing144. 最长异或值路径 ##

1.  题目描述  
    给定一个树，树上的边都具有权值。树中一条路径的异或长度被定义为路径上所有边的权值的异或和，给定具有n个节点的树，你能找到异或长度最大的路径吗？  
    **输入格式**  
    第一行包含整数n，表示树的节点数目。  
    接下来n-1行，每行包括三个整数u，v，w，表示节点u和节点v之间有一条边权重为w。  
    **输出格式**  
    输出一个整数，表示异或长度最大的路径的最大异或和。  
    **数据范围**  
     1 ≤ n ≤ 100000 , 0 ≤ u , v < n , 0 ≤ w < 2 31 1≤n≤100000 , 0≤u,v<n, 0≤w<2^\{31\} 1≤n≤100000,0≤u,v<n,0≤w<231  
    **输入样例**  
    4  
    0 1 3  
    1 2 4  
    1 3 6  
    **输出样例**  
    7
2.  代码

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const int N = 100010, M = 3000000;
    
    typedef struct Edge{
        
        int t, l;
    }Edge;
    
    vector<Edge> edges[N];
    vector<int> vis(N, 0);
    int arr[N];
    int n;
    int son[M][2], idx;
    
    void insert(int k)
    {
        
        int p = 0;
        for(int i = 30; ~i; --i)
        {
        
            int &s = son[p][k >> i & 1];
            if(!s) s = ++idx;
            p = s;
        }
        return;
    }
    
    int query(int k)
    {
        
        int res = 0;
        int p = 0;
        for(int i = 30; ~i; --i)
        {
        
            int x = k >> i & 1;
            if(son[p][!x])
            {
        
                res <<= 1;
                res |= !x;
                p = son[p][!x];
            }
            else
            {
        
                res <<= 1;
                res |= x;
                p = son[p][x];
            }
        }
        
        return res;
    }
    
    void dfs(int p, int sum)
    {
        
        vis[p] = true;
        arr[p] = sum;
        for(int i = 0;i < edges[p].size(); ++i)
        {
        
            sum ^= edges[p][i].l;
            if(!vis[edges[p][i].t]) dfs(edges[p][i].t, sum);
            sum ^= edges[p][i].l;
        }
        return;
    } 
    
    
    int main()
    {
        
        cin >> n;
        for(int i = 0, u, v ,d;i < n - 1;++i)
        {
        
            cin >> u >> v >> d;
            edges[u].push_back({
        v, d});
            edges[v].push_back({
        u, d});
        }
    
        dfs(0, 0);
        for(int i = 0;i < n;++i)
        {
        
            insert(arr[i]);
        }
        
        int res = 0;
        for(int i = 0;i < n;++i)
        {
        
            res = max(res, query(arr[i]) ^ arr[i]);
        }
        cout << res << endl;
        
        return 0;
    }