Trie、並查集、堆、Hash表學習過程以及遇到的問題

• 2021 年 3 月 30 日
• 筆記
• 數據結構與算法

Trie、並查集、堆、Hash表：

Trie

快速存儲和查找字符串集合 字符類型統一，將單詞在最後一個字母結束的位置上打上標記

練習題：Trie字符串統計

import java.util.*;

public class Main{
    static int N = 100010;
    static int[][] son = new int[N][26];
    static int[] con = new int[N];
    static int idx =0;
    static char[] str = new char[N];
    // 插入操作
    public static void insert(char[] str){
        // 初始化根節點
        int p = 0;
        // 遍歷字符串的每個字符
        for(int i = 0; i < str.length; i++){
            //將字母映射為數組  'a'-->97;
            int u = str[i] -'a';
            //如果子節點沒有 及：son[p][u] ==0;
            //那麼 添加節點
            if(son[p][u] == 0) son[p][u] = ++idx;
            //更新節點位置
            p = son[p][u];
        }
        //統計最後以str[p]這個結尾的字母
        con[p]++;
    }
    // 查找操作
    public static int select(char[] str){
        //初始化根節點
        int p = 0;
        for(int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            //如果子節點==0；代表沒有所查找的字母，及沒有該單詞，返回0次
            if(son[p][u] == 0) return 0;
            p = son[p][u];
        }
        //最後遍歷完成後p就是以str[p]的字母
        //返回單詞的次數
        return con[p];
        
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        while(n-- != 0){
            String common = sc.next();
            String str = sc.next();
            if(common.equals("I")){
                //toCharArray() -->將字符串轉為字符數組
                insert(str.toCharArray());
            }else if(common.equals("Q")){
                System.out.println(select(str.toCharArray()));
            }
        }
        
    }
}

最大異或對：

暴力方法：

public class Main{
    static int res = 0;
    public static void main(String[] args){
        for(int i = 0; i < n; i++){  //枚舉第一個數
            for(int j = 0; j < i; j++){  //枚舉第二個數
                res  = Math.max(res,a[i] ^ a[j]); 
            }
        }
        System.out.println(res);
    }
    
}

使用Trie樹來做：

import java.util.*;

public class Main{
    static int N = 100010,M = 3000000;
    static int[] a = new int[N];
    //樹的長度最多不超過N*31,節點為0，1；
    static int[][] son = new int[M][2];
    static int idx;
    
    // 創建Trie
    public static void insert(int a){
        int p = 0;
        for(int i = 30; i >= 0; i--){
            // 判斷a的二進制位的第i個數是0還是1;
            int s = a >> i & 1;
            if(son[p][s] == 0) son[p][s] = ++idx;
            p = son[p][s];  //把當前節點移動到下一節點;
        }
    }
    // 查詢
    public static int query(int a){
        int p = 0,res = 0;
        for(int i = 30; i >= 0; i--){
            //判斷數字a在第i位的二進制是0還是1;
            int s = a >> i&1;
            //要想使得a^x最大，那麼x要最小，也就是x得二進制與a二進制相反才行
            //判斷子節點與當前a中二進制相反得分支存不存在(不存在 son[p][1-s] ==0);
            if(son[p][1-s] != 0){
                //二進制轉十進制操作
                //原：3-->110,查：001; index:2、1、0；
                //查到一位轉換成十進制相加即等於最後與原數異或為最大值
                res = res + (1<< i);
                //更新p位置，即往下走下一節點（相反得一條路）
                p = son[p][1-s];
            //查找得分支點沒有得話，只能走已存在得分支;
            }else p = son[p][s];
        }
        //返回結果
        return res;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        for(int i = 0; i < n; i++){  //初始化數組
            a[i] = sc.nextInt();
            insert(a[i]);
        }
        //遍曆數組中所有得元素，找到數組中異或得最大得數；
        for(int i = 0; i < n; i++){
            //query返回得使a[i]^x最大得值
            res  = Math.max(res,query(a[i]));
        }
        System.out.println(res);
        
    }
    
}

問題匯總:

開的son中，第一個取得M是什麼含義。
Trie樹得深度不是31嗎，那隻開31個空間不久好了嗎？

答：

son的第一維度存的是trie數一共有多少節點，如果是存儲一個數的話，確實開31個空間就好了，但是存儲的是N = 100000個數，每個數循環31次，那就是31*100000 = 310w，因為會有復用的節點，用不上這麼多，300w就可以了

問：

int 是32位的，請問在對一個數進行遍歷，判斷該位是否為1時，為啥是從30~0；不用關心第31位嗎？

答：

題目中規定了 0 ≤ Ai <2^31，所以循環到30就夠了

問：

什麼是從i=30開始而不是0

答：

因為是求最大值，所以從最高位開始比較，要有限保證最高位為1

並查集：O(1)

1、 將兩個集合合併

2、 詢問兩個元素是否再一個集合當中

基本原理：每個集合用一顆樹來表示，樹根的編號就是整個集合的編號，每個節點存儲它的父節點，p[x]表示x的父節點；

問題一：如何判斷樹根：if(p[x] == x) x就是樹根

問題二：如何求x的集合編號：while(p[x] != x) x = p[x]—->包含路徑壓縮算法（優化）

問題三：如何合併兩個集合：px是x的集合編號，py是y的集合編號，p[x] = y

核心操作：

public static void find(int x){ // 返回x的祖宗節點 + 路徑壓縮
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

樸素並查集–無擴展

import java.util.*;
public class Main{
    // 每個集合用樹來存儲
    static int N = 100010;
    // 建立父節點數組
    static int[] p = new int[N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 初始化父節點數組
        for(int i = 1; i <= n; i++) p[i] = i;
        
        while(m-- != 0){
            char s = sc.next().charAt(0);
            
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if(s == 'M'){
                //將a根節點的父節點指向b的根節點--》實現兩個集合的合併
                p[find(a)] = find(b);
            }else{
                // 如果a的根節點等於b的根節點-->在同一個集合中
                if(find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
    // 返回x的根節點
    public static int find(int x){
        // 如果父節點不等於根節點，則遞歸尋找
        if(p[x] != x)  p[x] = find(p[x]);
        //返回x的所在的根節點
        return p[x];
    }
    
}

以下擴展情況：維護集合大小

import java.util.*;

public class Main{
    static int N = 100010;
    // 每個集合
    static int[] p = new int[N];
    // 每個集合的大小
    static int[] size = new int[N];
    
    // 返回集合（x）的跟節點
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 對每個集合以及集合大小進行初始化
        for(int i = 0; i < n; i++){
            p[i] = i;
            size[i] = 1;
        } 
        
        while(m -- != 0){
            
            String s = sc.next();
            if(s.equals("C")){
                int a = sc.nextInt();
                int b = sc.nextInt();
                //不加判斷，當a與b集合相同時， 執行了自己加自己，不符合題意，需要特判
                if(find(a) != find(b)){
                    // 合併後的連通塊數量（有多少個點）
                    size[find(b)] += size[find(a)];
                    // a集合的父節點執行b集合
                    p[find(a)] = find(b);
                }
                
            }
            else if(s.equals("Q1")){
                int a = sc.nextInt();
                int b = sc.nextInt();
                
                if(find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
            else{
                int a = sc.nextInt();
                // 查詢a所在集合的連通塊大小，找到a的根，並統計根的數量
                System.out.println(size[find(a)]);
            }
        }
    }
    
}

堆：

堆:就是一個用一維數組來表示一個完全二叉樹的這麼一個數據結構。所謂二叉樹就是一種樹，每一個父節點，有最多兩個子節點，一般叫做左右子樹

完美二叉樹：是一個二叉樹層數為k的時候，它的元素數量等於2k-1

而一個完全二叉樹可以理解為是一個完美二叉樹缺少一部分或者不缺少一部分的二叉樹，但是內容一定是從上到下，從左到右的填充，也就是缺少的部分總在右邊；

小根堆： 即根節點小於等於它的左孩子,也小於等於它的右孩子，且每個點都小於左右子節點；左孩子是左邊集合的最小值，右孩子是右邊的最小值

根節點是左右孩子的最小值—>推論出：根節點為堆的最小值

如何手寫一個堆：

size–>表示堆的大小；

1. 插入一個數：

   heap[++size] = x;
   up(size);
   

2. 求集合當中的最小值

   heap[1];
   

3. 刪除最小值：

   heap[1] = heap[size];
   size--;
   down(1);
   

4. 刪除任意一個元素：

   heap[k] = heap[size];
   size--;
   down(k);
   up(k);
   

5. 修改任意一個元素：

   heap[k] = x;
   down(k);
   up(k);
   

堆排序：

步驟：（輸出前m個的最小值）

1. 初始化堆
2. 建堆
3. down操作

其中down操作的實現過程：

比較三個點的最小值，如果不符合堆的定義那麼就交換、遞歸執行down操作

import java.util.*;
import java.io.*;

public class Main{
    static int N = 100010;
    // 定義堆
    static int[] h = new int[N];
    // 確定堆的大小
    static int size;
    
    // 當數在三個數中大時，使數往下沉
    public static void down(int u){
        // 設三個數的最小值為t;
        int t = u;
        // u*2為 u的左兒子； u*2+1 為u的右兒子；
        // 如果左兒子的下標小於堆的大小，則表示存在這個點；
        // 並且左兒子值比最小t的值小,則將t指向左兒子
        if(u*2 <= size && h[u*2] < h[t]) t = u * 2;
        // 如果右兒子的下標小於堆的大小，則表示存在這個點；
        // 並且右兒子值比最小t的值小,則將t指向右兒子
        if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
        // 如果最後t的最小值不是自己(u);
        // 那麼交換兩個下標所在的值;交換完在down一下,防止破壞堆結構;
        if(t != u){
            int temp = h[u];
            h[u] = h[t];
            h[t] = temp;
            down(t);
        }
        
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] s = br.readLine().split(" ");
        
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        
        String[] str = br.readLine().split(" ");
        // 初始化堆
        for(int i = 1; i <= n; i++){
            h[i] = Integer.parseInt(str[i-1]);
        }
        // 設置堆的大小
        size = n;
        //通過遞推可得到時間複雜度：建堆-->時間複雜度為O(n)
        for(int i = n/2;i != 0;i--){
            down(i);
        }
        
        while(m-- != 0){
            // 輸出最當前最小值,也就是堆頂
            bw.write(h[1]+" ");
            // 將最後的值覆蓋掉堆頂--就是刪掉堆頂
            h[1]  =h[size];
            // 堆大小--
            size--;
            // 在把堆頂down一下  找出最小值;
            down(1);
        }
        
        bw.flush();
        br.close();
        bw.close();
    }
    
}

實現up操作：

u/2為u的父節點，h[u] < h[u/2]–>子節點小於父節點；交換完後，up(u父節點的父節點)；

首先堆是完全二叉樹：(以下是編號)

  1
 2  3
4 5 6 7

2 / 2 = 1, 3 / 2 = 1.
4 / 2 = 2, 5 / 2 = 2, 6 / 2 = 3, 7 / 2 = 3

通過上面操作就能找到父節點；

public static void up(int u){
        if(u / 2 > 0 && h[u] < h[u / 2]){
            heapSwap(u, u / 2);
            up(u/2);
        }
    }

模擬堆：

import java.util.*;
import java.io.*;

public class Main{
    static int N = 100010;
    static int[] h = new int[N];
    static int[] ph = new int[N]; //存放第k個點的值的下標
    static int[] hp = new int[N]; //存放隊中點的值是第幾個插入的
    static int size;  //size 記錄的是堆當前的數據多少
    
    public static void down(int u){
        int t = u;
        if(u*2 <=size && h[u*2] < h[t]) t = u*2;
        if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
        if(t != u){
            heap_swap(u,t);
            down(t);
        }
    }
    public static void up(int u){
        if(u / 2 > 0 && h[u] < h[u / 2]){
            heap_swap(u,u/2);
            up(u/2);
        }
    }
    
    public static void heap_swap(int u,int v)
    {   
        // 相對照
        // swap(h[u],h[v]);   //值交換 
        // swap(hp[u],hp[v]);  //堆中點的插入順序（編號）交換
        // swap(ph[hp[u]],ph[hp[v]]); //對編號第h[u] h[v]的值交換
        
        swap(h,u,v);
        swap(hp, u, v);
        swap(ph, hp[u], hp[v]);
    
    }
    
    public static void swap(int[] a, int u, int v){
        int tmp = a[u];
        a[u] = a[v];
        a[v] = tmp;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        size = 0;
        int m = 0;  
        
        while(n-- != 0){
            String[] s = br.readLine().split(" ");
            String op = s[0];
            if("I".equals(op)){
                int x = Integer.valueOf(s[1]);
                m++;
                h[++size]=x;
                // ph[m]=size;
                // hp[size]=m;
                // 建立映射關係即：第m個插入的數的編號是size;
                ph[m] = size;
                //第size編號下的是第m個插入的數；
                hp[size] = m;
                // 將插入的數向上調整
                up(size);
            }else if("PM".equals(op))    bw.write(h[1]+"\n");
            else if("DM".equals(op)){
                heap_swap(1,size);
                size--;
                down(1);
            }else if("D".equals(op)){
                int k = Integer.parseInt(s[1]);
                int u=ph[k];                //這裡一定要用u=ph[k]保存第k個插入點的下標
                heap_swap(u,size);          //因為在此處heapSwap操作後ph[k]的值已經發生 
                size--;                    //如果在up,down操作中仍然使用ph[k]作為參數就會發生錯誤
                up(u);
                down(u);
            }else if("C".equals(op)){
                int k = Integer.parseInt(s[1]);
                int x = Integer.parseInt(s[2]);
                h[ph[k]]=x;                 //此處由於未涉及heapSwap操作且下面的up、down操作只會發生一個所以
                down(ph[k]);                //所以可直接傳入ph[k]作為參數
                up(ph[k]);
            }
        }
        bw.flush();
        br.close();
        bw.close();
        
    }
    
}

哈希表：

求質數：

import java.util.Scanner;

public class 求質數 {
    public static void main(String[] args) {
       for(int i = 100000;;i++){
           boolean flag = true;
           for(int j = 2; j* j <= i; j++){
               if(i % j == 0){
                   flag = false;
                   break;
               }
           }
           if(flag){
               System.out.println(i);
               break;
           }
       }
    }
}

拉鏈法：

import java.util.*;
import java.io.*;
public class Main{
    //h[]是哈希函數的一維數組
    //N為數據範圍外的最小質數
    //模N這個數一般要取成質數且離2的整次冪儘可能的遠---減少哈希衝突的概率
    static int N = 100003;
    static int[] h = new int[N];
    //e[]是鏈表中存的值
    static int[] e = new int[N];
    //ne[]是指針存的指向的地址
    static int[] next = new int[N];
    //idx是當前指針
    static int idx;
    // 插入操作
    public static void insert(int x){
        //對負數的處理,k是哈希值
        //如果x%N的餘數為零，+N則一定為正數，然後再取模
        int k = (x % N + N) % N;
        // 單鏈表的實現
        //頭插法
        e[idx] = x;
        next[idx] = h[k];
        h[k] = idx++;
    }
    // 查找元素是否存在
    public static boolean find(int x){
        int k = (x% N + N) % N;
        for(int i = h[k]; i != -1; i=next[i]){
            //找到返回true
            if(e[i] == x) return true;
        }
        return false;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //初始化h[]
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(n-->0){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            if(s[0].equals("I")){
                insert(x);
            }else{
                if(find(x))System.out.println("Yes");
                else    System.out.println("No");
            }
        }
    }
    
}

開放尋址法：

好處：只開一個數組即可；

package ACWing.數據結構與算法;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 開放尋址法_哈希表 {
    //一般開到範圍的兩到三倍
    //N的值也需要取模判斷一下
    static int N= 200003;
    static int[] h = new int[N];
    //設當前值不在題目給出的範圍中，表示當前無數據--空數據
    static int bound = (int)(1e9+1);

    public static int  find(int x){
        int k = ( x % N + N) % N;
        //如果當前空間有數據，且該空間的數據不等於我們要查找的數據
        //那麼繼續往下尋找
        while(h[k] != bound && h[k] != x){
            k++;
            if(k== N) k = 0;
        }
        //返回的情況有兩種
        /*
        1、k指代的是當前的空間沒有人
        2、k指代的是當前的空間有人且就是我們要查找的元素
        */
        return k;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++) h[i] = bound;
        while(n-- != 0){
            String[] s = br.readLine().split(" ");
            String op = s[0];
            int x = Integer.parseInt(s[1]);
            int k = find(x);
            if(op.equals("I")){
                h[k] = x;
            }else{
                //如果當前元素不為空
                if(h[k] != bound) System.out.println("Yes");
                //為空
                else System.out.println("No");
            }
        }
        br.close();
    }
}

字符串哈希方式：

1. 先將字符串轉換成P進制的數字；
2. 然後求出前綴和的哈希值

怎麼求前綴和的哈希值：

將字符串看成P進制的數：

例：求ABCD的哈希值

看成P進制的話，該字符串有四位：

如果數據量太大的話，我們需要mod上一個Q，通過取模可以映射到（0-Q-1）上的數

注意：

不能映射為0，因為0與任何數進行運算都為零，這樣會造成數據重複；

當映射的時候必定會出現兩個不同的數取模成相同的數

解決的方法：假定人品足夠好，不會出現衝突，且經驗取值為：P=131或者13331，Q=2^64次方的時候，可以避免99.99%的衝突；

求哈希值：

h[]數組表示前綴和的哈希值；

h[R] : 1-R的前綴和hash值

h[L-1] : 1-(L-1)的前綴和hash值

在h[R]中：

在h[L-1]中:

我們的目標時求出L-R的前綴和哈希值，以下看圖說話

對於區間和公式的理解：h[l,r]=h[r]−h[l−1]×P^(r−l+1)

求L-R 也就是求D-E,也就是求4-5

123*100= 12300；12345-12300 = 45；

ABC*100 = ABC00; ABCDE-ABC=DE;

h[R]-h[L-1]*P^(R-1-(L-2));

h[R] – h[L-1]*P^(R-L+1)

解題步驟：

1. 先保存每位的權值；
2. 求每個字符的前綴和哈希值
3. 獲取區間的前綴和哈希值
4. 調用函數進行比較

字符串前綴哈希法：

import java.util.*;
import java.io.*;
public class Main{
    static int N = 100010;
    static int h[] = new int[N];
    static int p[] = new int[N];
    static int P = 131;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        //輸入長度為n的字符串
        int n = Integer.parseInt(s[0]);
        //m次詢問
        int m = Integer.parseInt(s[1]);
        String str = br.readLine();
        p[0] =1;   //一定不要忘記設置為1；
        for(int i = 1; i <= n; i++){
            //預處理保存每位的權值
            p[i] = p[i-1]*P;
            //獲取前綴和哈希值
            h[i] = h[i-1]*P+str.charAt(i-1);
        }
        
        while(m-- != 0){
            String[] s1 = br.readLine().split(" ");
            int l1 = Integer.parseInt(s1[0]);
            int r1 = Integer.parseInt(s1[1]);
            int l2 = Integer.parseInt(s1[2]);
            int r2 = Integer.parseInt(s1[3]);
            if(getHash(l1,r1) == getHash(l2,r2)) bw.write("Yes"+"\n");
            else bw.write("No"+"\n");
        }
        bw.flush();
        br.close();
        bw.close();
    }
    public static long getHash(int l,int r){
        return h[r] - h[l-1]*p[r-l+1];
    }
}