字典樹與01trie

字典樹簡介

當我們通過字典查一個字或單詞的時候，我們會通過前綴或關鍵字的來快速定位一個字的位置，進行快速查找。

字典樹就是類似字典中索引表的一種數據結構，能夠幫助我們快速定位一個字符串的位置。

字典樹是一種存儲字符串的數據結構，除了根節點，每個節點可以存儲一個字符，從根節點到樹上某一結點的路徑代表一個字符串

在向字典樹中添加字符串的時候，如果一個字符串在某個節點結束，我們可以給這個節點打上一個標記。這樣在后續訪問時就可以知道到此節點為止為以一個完成的字符串。

const int N=1e5+10;
//第一維表示節點標號，第二維表示該節點到下一節點
int nxt[N][26];
//標記數組
bool isend[N];
//根節點和樹的元素個數
int root=0,cnt=0;

字典樹的插入

void insert(char s[],int len)
{int now=0;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;//當原樹中不存在這一條路徑時，添加節點，創建路徑now=nxt[now][x];}isend[now]=true;
}

?字典樹的查找

bool search(char s[],int len)
{int now=0;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])return false;now=nxt[now][x];}return isend[now];
}

?字典樹的刪除的情況比較少見

這時候我們要記錄每個數節點的子樹大小，這里的子樹大小是指在這個節點下有幾個真實存在的字符串。

對于要刪除的字符串，先用查找字符串的方式找到該字符串在字典樹中的最后一個節點，刪除標記，然后回溯整條路徑，如果路徑上節點的子樹大小為零，就可以刪除這個節點

//刪除操作需要有一個e數組
//e[x],表示的是經過x節點有幾個字符串
//在刪除操作時，需要將該字符串經過的路徑e[x]--
//當發現該節點e[x]為1時，就說明只有這一條字符串經過該路徑，將此節點刪除，就將該字符串成功刪除
int e[N]
void insert(char s[],int len)
{int now=0;e[now]++;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;now=nxt[now][x];e[now]++;}isend[now]=true;
}
void remove(char s[],int len)
{int now=0;e[now]--;for(int i=1;i<=len;i++){int x=s[i]-'a';int tmp=nxt[now][x];if(e[tmp]==1)e[now][x]=0;//刪除操作now=tmp;e[tmp]--;}isend[now]=false;
}

寫一道例題藍橋3755小藍的神秘圖書館

?

?

ac代碼如下

#include<iostream>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
int nxt[N][26];
ll e[N];
int cnt = 0;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){string str; cin >> str;int len = str.length();int now = 0;e[now]++;for (int j = 0; j < len; j++){int x = str[j] - 'a';if (!nxt[now][x]){nxt[now][x] = ++cnt;}now = nxt[now][x];++e[now];}}while (m--){string str; cin >> str;int len = str.length();int now = 0;bool flag = true;for (int j = 0; j < len && flag; j++){int x = str[j] - 'a';if (!nxt[now][x]){flag = false;}else now = nxt[now][x];}if (flag){cout <<e[now] << endl;}else cout << 0 << endl;}return 0;
}

?字典樹除了可以對字符串進行前綴判定，還可以對字符串進行排序

原理就是既然字典樹是一顆樹，那我們就可以以遍歷樹的方式來遍歷字典樹，字典樹的每一節點都有26條向下的邊(當然大部分邊是不存在的)我們優先往小的字典序遍歷，進行一次dfs就可以對所有的字符串進行排序了

上例題

?代碼如下

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e5 + 10;
int nxt[N][26];
int cnt = 0,n;
bool isend[N];
int str[30];
void dfs(int x, int deep)
{if (isend[x]){for (int i = 1; i <= deep; i++)cout << (char)(str[i]+'a');cout << endl;}for (int i = 0; i < 26; i++){if (nxt[x][i]){str[deep + 1] = i;dfs(nxt[x][i], deep + 1);}}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;int len = s.length();int now = 0;for (int j = 0; j < len; j++){int x = s[j] - 'a';if (!nxt[now][x])nxt[now][x] = ++cnt;now = nxt[now][x];}isend[now] = true;}dfs(0, 0);return 0;
}

最后可以用字典樹來求解最長公共前綴問題

?

以樹的方式來看這個問題，求任意兩個字符串的最長公共前綴，其實就是求解兩個節點的最近公共祖先，那就得到了最長公共前綴

求解LCA問題，依舊可以使用倍增的思想

代碼如下

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e5 + 10;
int nxt[N][26];
int cnt = 0,n,m;
int ed[N],fa[N][30];
int d[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;int len = s.length();int now = 0;for (int j = 0; j < len; j++){int x = s[j] - 'a';if (!nxt[now][x]){nxt[now][x] = ++cnt;fa[cnt][0] = now;d[cnt] = d[now] + 1;//記錄深度}now = nxt[now][x];}ed[i] = now;//記錄每一個字符串的結束節點}//倍增求LCAfor (int i = 1; i <= 20; i++){for (int j = 1; j <= cnt; j++){if (fa[j][i - 1]){fa[j][i] = fa[fa[j][i - 1]][i - 1];}}}cin >> m;while (m--){int x, y; cin >> x >> y;x = ed[x], y = ed[y];if (d[x] < d[y])swap(x, y);int z = d[x] - d[y];for (int i = 0; i <= 20&&z; i++, z >>= 1){if (z & 1)x = fa[x][i];}if (x == y){cout << d[x] << endl;continue;}for (int i = 20; i >= 0; i--){if (fa[x][i] != fa[y][i]){x = fa[x][i];y = fa[y][i];}}cout << d[fa[x][0]] << endl;}return 0;
}

?接下來是01trie

01trie是一種二叉樹，每一個葉子節點對應一個二進制數，通過從根出發到該節點的路徑表示，深度小的表示二進制高位

01trie通常用于解決最大異或對問題，即求解a[i]^a[j]的最大值的問題

01trie支持三種操作

1.插入元素x

2.查詢01trie中與x異或后最大的元素

3.查詢比x更大的元素個數，可用于解決逆序對問題

還可以結合二分等算法實現更多操作

這樣就可以創建一個01trie，與字典樹幾乎一樣

01trie的插入

void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){  int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}

01trie的查詢

//查詢01trie中與x異或的最大值
int query(int x)
{int now=1;int res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y])now=nxt[now][!y],res+=(1<<i);else now=nxt[now][y];}return res;
}
//查詢01trie中比x大的數目
int query(int x)
{int res=0;int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(y==0)res+=e[nxt[now][1]);if(!nxt[now][y])break;now=nxt[now][y];}return res;
}

?下面來寫一道例題藍橋17205卓兒的最大異或和

考慮異或的性質，將前綴異或添加到字典樹中，每次詢問求與當前前綴異或的最大值，就可以詢問到每一個區間，每次取max就能得到答案

ac代碼如下

#include<iostream>
using namespace std;
using ll=long long;
const int N=32*1e5+10;
int nxt[N][2];
int n,cnt=1;
ll pre[N];
void insert(int x)
{int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];}
}
ll query(ll x)
{int now=1;ll res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y])now=nxt[now][!y],res+=(1ll<<i);else now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;int x;ll ans=-1;insert(0);for(int i=1;i<=n;i++){cin>>x;pre[i]=pre[i-1]^x;ans=max(ans,query(pre[i]));insert(pre[i]);}cout<<ans<<endl;
}

?接下來是關于01trie刪點求最大異或

藍橋19721最大異或和

考慮枚舉每一個節點，然后刪除與它相鄰的節點，求一次最大異或和，再將點添加回去

ac代碼如下

#include<iostream>
#include<vector>
using namespace std;
const int N=32*1e5+5;
int nxt[N][2];
int e[N];
int n,cnt=1;
void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}
void remove(int x)
{int now=1;e[now]--;for(int i=30;i>=0;i--){int y=(x>>i)&1;now=nxt[now][y];e[now]--;}
}
int query(int x)
{int res=0;int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y]&&e[nxt[now][!y]])now=nxt[now][!y],res|=(1<<i);else now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>a(n+1);vector<vector<int>> p(n+1,vector<int>());for(int i=1;i<=n;i++){cin>>a[i];insert(a[i]);}for(int i=1;i<=n;i++){int x;cin>>x;if(x!=-1){p[x+1].push_back(i);p[i].push_back(x+1);}}int ans=0;for(int i=1;i<=n;i++){for(auto y:p[i])remove(a[y]);ans=max(ans,query(a[i]));for(auto y:p[i])insert(a[y]);}cout<<ans<<endl;
}

最后來用01trie求逆序對

?

建樹，然后就求出來了

#include<iostream>
#include<vector>
using namespace std;
using ll=long long;
const int N=32*1e5+10;
int nxt[N][2],e[N],n,cnt=1;
void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}
int query(int x)
{int now=1;int res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(y==0)res+=e[nxt[now][1]];if(!nxt[now][y])break;now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;ll ans=0;for(int i=1;i<=n;i++){int x;cin>>x;insert(x);ans+=query(x);}cout<<ans<<endl;
}

?歐克了

?

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/75604.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/75604.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/75604.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

二十五、實戰開發 uni-app x 項目（仿京東）- 前后端輪播圖

二十五、實戰開發 uni-app x 項目（仿京東）- 前后端輪播圖

定義了一個名為 Swiper 的Java類，用于表示一個輪播圖實體。它使用了 Jakarta Persistence API (JPA) 來映射數據庫表，并使用了 Lombok 庫來簡化代碼。以下是對代碼的詳細講解： 1. 包聲明 package com.jd.jdmall.model; 這行代碼聲明了該類所在的包路徑為 com.jd.jdmall.mode…
閱讀更多...
游戲搖桿開發：利用 Windows API 實現搖桿輸入捕獲

游戲搖桿開發：利用 Windows API 實現搖桿輸入捕獲

在現代游戲開發中&#xff0c;游戲搖桿&#xff08;Joystick&#xff09;作為一種重要的輸入設備&#xff0c;能夠為玩家提供更加沉浸式的游戲體驗。Windows 操作系統提供了一系列 API 函數&#xff0c;允許開發者輕松地捕獲和處理游戲搖桿的輸入。本文將介紹如何使用 Windows …
閱讀更多...
Ceph集群2025（Squid版）快速對接K8S cephFS文件存儲

Ceph集群2025（Squid版）快速對接K8S cephFS文件存儲

ceph的塊存儲太簡單了。所以不做演示 查看集群 創建一個 CephFS 文件系統 # ceph fs volume create cephfs01 需要創建一個子卷# ceph fs subvolume create cephfs01 my-subvol -----------------#以下全部自動創建好 # ceph fs ls name: cephfs01, metadata pool: c…
閱讀更多...
Python中數據結構元組詳解

Python中數據結構元組詳解

在Python中&#xff0c;元組&#xff08;Tuple&#xff09;是一種不可變的序列類型&#xff0c;常用于存儲一組有序的數據。與列表&#xff08;List&#xff09;不同&#xff0c;元組一旦創建&#xff0c;其內容無法修改。本文將詳細介紹元組的基本操作、常見運算、內置函數以及…
閱讀更多...
游戲引擎學習第183天

游戲引擎學習第183天

回顧和今天的計劃 我對接下來的進展感到非常興奮。雖然我們可能會遇到一些問題&#xff0c;但昨天我們差不多完成了將所有內容遷移到新的日志系統的工作&#xff0c;我們正在把一些內容整合進來&#xff0c;甚至是之前通過不同方式記錄時間戳的舊平臺層部分&#xff0c;現在也…
閱讀更多...
Spring 如何處理循環依賴

Spring 如何處理循環依賴

在 Spring 框架里&#xff0c;循環依賴指的是多個 Bean 之間相互依賴&#xff0c;從而形成一個閉環。例如&#xff0c;Bean A 依賴 Bean B&#xff0c;而 Bean B 又依賴 Bean A。Spring 主要通過三級緩存機制來處理循環依賴&#xff0c;下面詳細介紹相關內容。 1. 三級緩存的定…
閱讀更多...
Android開發layer-list

Android開發layer-list

Android開發layer-list 它的用處可以在drawable上進行多圖拼接&#xff0c;比如啟動頁&#xff0c;不想圖片被拉伸就這么做。還有做某些線突出來。 示例代碼&#xff1a; <?xml version"1.0" encoding"utf-8"?> <layer-list xmlns:android&q…
閱讀更多...
手機測試，工作中學習

手機測試，工作中學習

要學習各種機型的截圖方式、開發模式在哪。 榮耀機型&#xff1a;截圖&#xff1a;關節快速敲兩下。開發者模式在“系統和更新”里。 1.出現缺陷&#xff0c;需要獲取日志。 學習adb生成日志&#xff1a;當測試中出現缺陷的&#xff0c;使用adb logcat -d > d:/log.txt …
閱讀更多...
OBS虛擬背景深度解析：無需綠幕也能打造專業教學視頻（附插件對比）

OBS虛擬背景深度解析：無需綠幕也能打造專業教學視頻（附插件對比）

想要錄制教學視頻卻苦于背景雜亂&#xff1f;本文將手把手教你用OBS實現專業級虛擬背景效果&#xff0c;無需綠幕也能輕松營造沉浸式教學場景。文末附6個提升畫面質感的免費背景資源&#xff01; 一、虛擬背景的核心價值&#xff1a;從「教師宿舍」到「虛擬講堂」的蛻變 我們調…
閱讀更多...
零基礎搭建智能法律知識庫！騰訊云HAI實戰教程

零基礎搭建智能法律知識庫！騰訊云HAI實戰教程

為什么需要法律知識庫&#xff1f; 想象一下&#xff0c;你的所有法律文件都在手邊&#xff0c;隨時可以搜索和分析。這就是法律知識庫的魅力所在。對于法律專業人士、處理大量法律文檔的企業&#xff0c;甚至是希望了解法律事項的普通人來說&#xff0c;法律知識庫都是一個不…
閱讀更多...
Rust從入門到精通之進階篇：19.Rust 生態系統

Rust從入門到精通之進階篇：19.Rust 生態系統

Rust 生態系統 Rust 擁有一個豐富而活躍的生態系統&#xff0c;提供了各種庫和框架來支持不同領域的開發。在本章中&#xff0c;我們將探索 Rust 生態系統中的主要組件&#xff0c;了解常用的庫和工具&#xff0c;以及如何在項目中有效地使用它們。 Rust 包管理&#xff1a;C…
閱讀更多...
前端面試：如何去衡量用戶操作過程中否卡頓？

前端面試：如何去衡量用戶操作過程中否卡頓？

衡量用戶在應用中的操作是否卡頓是前端開發中的一個關鍵任務&#xff0c;涉及用戶體驗的各個方面。以下是一些常用的方法和工具&#xff0c;可以幫助你有效地評估用戶操作中的卡頓情況&#xff1a; 1. 使用性能分析工具 瀏覽器開發者工具&#xff1a;大多數現代瀏覽器&#xf…
閱讀更多...
Python技術棧與數據可視化創意實踐詳解（三）

Python技術棧與數據可視化創意實踐詳解（三）

Python在數據可視化領域憑借豐富的庫和靈活的生態系統&#xff0c;能夠實現從基礎圖表到復雜交互式可視化的全場景覆蓋。以下從技術選型、創意實現到實戰優化進行系統化解析&#xff0c;并提供可直接落地的代碼示例。 一、Python數據可視化技術棧 1. 基礎與統計可視化 Matplotl…
閱讀更多...
訂票系統|基于Java+vue的火車票訂票系統(源碼+數據庫+文檔)

訂票系統|基于Java+vue的火車票訂票系統(源碼+數據庫+文檔)

訂票系統目錄 基于Springbootvue的火車票訂票系統 一、前言 二、系統設計 三、系統功能設計 1會員信息管理 2 車次信息管理 3訂票訂單管理 4留言板管理 四、數據庫設計 五、核心代碼 六、論文參考 七、最新計算機畢設選題推薦 八、源碼獲取&#xff1a; 博主介紹…
閱讀更多...
Snowflake 算法的實現

Snowflake 算法的實現

snowflake(雪花算法)是一個開源的分布式 ID 生成算法&#xff0c;結果是一個 long 型的 ID。snowflake 算法將 64bit 劃分為多段&#xff0c;分開來標識機器、時間等信息&#xff0c;具體組成結構如下圖所示&#xff1a; snowflake 算法的核心思想是使用 41bit 作為毫秒數&…
閱讀更多...
C 語言中， scanf 函數在哪些情況下會結束輸入讀取：

C 語言中， scanf 函數在哪些情況下會結束輸入讀取：

在 C 語言中&#xff0c; scanf 函數在以下幾種情況下會結束輸入讀取&#xff1a; &#xff1a; 1. 遇到指定格式匹配失敗&#xff1a; scanf 按照格式字符串要求讀取輸入。當輸入數據格式與格式字符串不匹配時&#xff0c;就會結束讀取。例如 scanf(“%d”, &num) 要求輸…
閱讀更多...
括號合法題

括號合法題

一、括號合法題 2116. 判斷一個括號字符串是否有效 //采用從左往右和從右往左遍歷的貪心算法&#xff0c;分別保證前綴合法&#xff0c;后綴合法。public boolean canBeValid(String s, String locked) {int ns.length();if (n%21) return false;int num0;// 從左到右掃描&…
閱讀更多...
圖生生AI商品圖：一鍵更換商品，保留原背景

圖生生AI商品圖：一鍵更換商品，保留原背景

圖生生AI商品圖工具&#xff0c;推出 “更換商品”功能&#xff0c;只需上傳一張參考圖和自己的商品圖&#xff0c;AI自動完成商品替換&#xff0c;保留原背景&#xff0c;3秒生成專業級電商圖&#xff01;無需PS技能&#xff0c;無需復雜操作&#xff0c;真正實現 “一鍵換商品…
閱讀更多...
[7-01-03].SpringBoot3集成MinIo

[7-01-03].SpringBoot3集成MinIo

MinIO學習大綱 一、Spingboot整合MinIo 第1步&#xff1a;搭建SpringBoot項目&#xff1a; 第2步&#xff1a;引入minio依賴 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi&q…
閱讀更多...
Gradle Project import Eclipse

Gradle Project import Eclipse

Gradle Project import Eclipse
閱讀更多...
最新文章

Copyright @ 2022~2023