题目链接
208. 实现 Trie (前缀树) - 力扣（LeetCode）
421. 数组中两个数的最大异或值 - 力扣（LeetCode）
实现 Trie (前缀树)
前缀树是一种数据结构，一般用于高效存储和检索字符串的键。
classTrie {
TreeNoderoot;
classTreeNode{
TreeNode[] next;
booleanisEnd;
publicTreeNode(){
// 子节点的指针数组，长度为26，可以包含所有的小写字母
next=newTreeNode[26];
// 表示是否为字符串的结尾
this.isEnd=false;
}
}
publicTrie() {
// 初始化
root=newTreeNode();
}
publicvoidinsert(Stringword) {
TreeNodecur=root;
// 将当前字符串插入到前缀树中
for(charc : word.toCharArray()){
// 如果不存在那么新建一个前缀树节点，进行插入
// 如果存在那么指针移动到下一个节点，处理下一个字符
if(cur.next[c-'a'] ==null) cur.next[c-'a'] =newTreeNode();
cur=cur.next[c-'a'];
}
// 插入完毕标记到了结尾
cur.isEnd=true;
}
publicbooleansearch(Stringword) {
TreeNodecur=root;
for(charc: word.toCharArray()){
// 如果当前节点不存在，那么直接返回false，前缀树中没有这个字符串
if(cur.next[c-'a'] ==null) returnfalse;
cur=cur.next[c-'a'];// 继续处理下一个字符节点
}
returncur.isEnd; //返回是否结束，如果字符串没有结束那么也不包含该字符串
}
publicbooleanstartsWith(Stringprefix) {
TreeNodecur=root;
for(charc: prefix.toCharArray()){
// 如果不存在，那么不存在该前缀
if(cur.next[c-'a'] ==null) returnfalse;
cur=cur.next[c-'a'];
}
returntrue;
}
}
单词替换
使用前缀树构造一颗字典树，将所有的词根都放入到前缀树中，遍历句子中的每一个单词，对单词在字典中进行词根搜索，找到对应的词根，用找到的词根换当前单词
classSolution {
TrieNoderoot=newTrieNode();
classTrieNode{
TrieNode[] next ;
booleanisEnd;
publicTrieNode(){
next=newTrieNode[26];
isEnd=false;
}
}
// 将词根插入到字典树(前缀树)中
publicvoidinsert(Stringword,TrieNoderoot){
TrieNodenode=root;
for(charc:word.toCharArray()){
if(node.next[c-'a'] ==null) node.next[c-'a']=newTrieNode();
node=node.next[c-'a'];
}
node.isEnd=true;
}
// 查找字符串中的词根
publicbooleansearch(TrieNoderoot,Stringword){
TrieNodenode=root;
for(charc:word.toCharArray()){
if(node.isEnd==true) break;
if(node.next[c-'a'] ==null) returnfalse;
node=node.next[c-'a'];
}
returntrue;
}
// 进行替换
publicStringreplace(Stringword,TrieNoderoot){
StringBuildersb=newStringBuilder();
TrieNodenode=root;
for(charc: word.toCharArray()){
// 如果当前节点为末尾，跳出循环，返回当前找到的词根
if(node.isEnd) break;
// 处理下一个节点
node=node.next[c-'a'];
// 将当前词根加入到字符串中
sb.append(c);
}
returnsb.toString();
}
publicStringreplaceWords(List<String>dictionary, Stringsentence) {
// 插入词根
for(Strings: dictionary) insert(s,root);
String[] split=sentence.split(" ");
for (inti=0; i<split.length; i++) {
// 进行替换
if (search(root,split[i])) split[i] =replace(split[i],root);
}
StringBuildersb=newStringBuilder();
for(Strings: split){
sb.append(s+" ");
}
sb.deleteCharAt(sb.length()-1);
returnsb.toString();
}
}
实现一个魔法字典
classMagicDictionary {
classTrie {
booleanisFinished;
Trie[] child;
publicTrie() {
isFinished=false;
child=newTrie[26];
}
}
Trieroot;
publicMagicDictionary() {
root=newTrie();
}
publicvoidbuildDict(String[] dictionary) {
for (Stringword : dictionary) {
Triecur=root;
for (inti=0; i<word.length(); ++i) {
charch=word.charAt(i);
intidx=ch-'a';
if (cur.child[idx] ==null) {
cur.child[idx] =newTrie();
}
cur=cur.child[idx];
}
cur.isFinished=true;
}
}
publicbooleansearch(StringsearchWord) {
returndfs(searchWord, root, 0, false);
}
privatebooleandfs(StringsearchWord, Trienode, intpos, booleanmodified) {
if (pos==searchWord.length()) {
returnmodified&&node.isFinished;
}
intidx=searchWord.charAt(pos) -'a';
if (node.child[idx] !=null) {
if (dfs(searchWord, node.child[idx], pos+1, modified)) {
returntrue;
}
}
if (!modified) {
for (inti=0; i<26; ++i) {
if (i!=idx&&node.child[i] !=null) {
if (dfs(searchWord, node.child[i], pos+1, true)) {
returntrue;
}
}
}
}
returnfalse;
}
}
我觉得遍历查找的方式就很好了，前缀树多少有点绕圈子b(￣▽￣)d
classMagicDictionary {
String[] words;
/** Initialize your data structure here. */
publicMagicDictionary() {
}
publicvoidbuildDict(String[] dictionary) {
words=dictionary;
}
publicbooleansearch(StringsearchWord) {
for(Strings: words){
// 标记一个字符串中字符与词根中字符不同的个数
intdiff=0;
if(s.length() !=searchWord.length()) continue;
for(inti=0;i<searchWord.length();i++){
if(s.charAt(i) !=searchWord.charAt(i)) {
diff++;
// 大于1个那么直接跳出循环，返回false，不能够转换一次就和词根一样
if(diff>1) break;
}
}
// 如果为1，那么可以转换
if(diff==1) returntrue;
}
returnfalse;
}
}
单词的压缩编码
保留所有不是其他单词后缀的单词
将所有的字符倒着插入到前缀树中，如果找到了
classSolution {
publicintminimumLengthEncoding(String[] words) {
TrieNoderoot=newTrieNode();
HashMap<TrieNode,Integer>map=newHashMap();
for(inti=0;i<words.length;i++){
Strings=words[i];
TrieNodenode=root;
for(intj=s.length()-1;j>=0;j--){
// 倒着插入前缀树
// 得到当前节点
node=node.get(s.charAt(j));
}
// 将节点和当前字符的下标存入到map中
map.put(node,i);
}
intres=0;
for(TrieNodenode : map.keySet()){
// 遍历map
// 如果当前节点的count = 0，说明为叶子节点，叶子结点就是不是后缀的单词
// 取出map中的保存的下标，将所有不是后缀的单词长度相加
// +1 是 +#
if(node.count==0) res+=words[map.get(node)].length()+1;
}
returnres;
}
classTrieNode{
TrieNode[] children;
intcount;
publicTrieNode(){
children=newTrieNode[26];
count=0;
}
publicTrieNodeget(charc){
if(children[c-'a'] ==null){
// 前缀树中没有当前字符，创建前缀树节点
children[c-'a'] =newTrieNode();
count++; // 长度为1
}
// 如果前缀树中存在当前字符，那么该字符为某一个单词的后缀，直接返回当前节点，当前节点的值为1
// 后续判断中会用到
returnchildren[c-'a']; // 返回当前节点
}
}
}
键值映射
classMapSum {
TrieNoderoot;
HashMap<String,Integer>map;
publicMapSum() {
root=newTrieNode();
map=newHashMap();
}
// 插入
publicvoidinsert(Stringkey, intval) {
// 当前值-map中包含该键的值，增量
intd=val-map.getOrDefault(key,0);
// 将key和val存入到map
map.put(key,val);
TrieNodecur=root;
for(charc : key.toCharArray()){
// 遍历key的字符
// 字符节点为空，新建一个节点
if(cur.next[c-'a'] ==null){
cur.next[c-'a'] =newTrieNode();
}
// 继续处理下一个节点
cur=cur.next[c-'a'];
// 需要更新每个前缀对应的值
// 把每一个节点都加增量，以便后续计算以某前缀开头所有key的和
cur.val+=d;
}
}
// 以某前缀开头所有key的和
publicintsum(Stringprefix) {
TrieNodecur=root;
for(charc: prefix.toCharArray()){
// 如果当前节点为空，那么没有前缀树中不存在该前缀，直接返回0
if(cur.next[c-'a'] ==null) return0;
cur=cur.next[c-'a'];
}
// 直接返回当前节点的值，就为和
returncur.val;
}
classTrieNode{
TrieNode[] next;
intval;
publicTrieNode(){
next=newTrieNode[26];
val=0;
}
}
}
这道题我也觉得HashMap最好用，直接使用哈希中封装好的函数👍
classMapSum {
HashMap<String,Integer>map;
/** Initialize your data structure here. */
publicMapSum() {
map=newHashMap();
}
publicvoidinsert(Stringkey, intval) {
map.put(key,val);
}
publicintsum(Stringprefix) {
intres=0;
for(Strings:map.keySet()){
if(s.startsWith(prefix)) res+=map.get(s);
}
returnres;
}
}
数组中两个数的最大异或值
异或就是当位两个数的值不同才为1，所以需要尽量找到一个与当前位不同的数
先确定高位，再确定低位，才能保证最大 ，接着一位一位去确定这个数位的大小
classSolution {
classTrieNode{
TrieNode[] next;
publicTrieNode(){
next=newTrieNode[2];
}
}
TrieNoderoot=newTrieNode();
publicintfindMaximumXOR(int[] nums) {
intmax=Integer.MIN_VALUE;
for (intnum:nums){
inster(num);
max=Math.max(max,maxOR(num));
}
return max;
}
publicvoidinster(intnum){
TrieNodenode=root;
// 倒着取出，先得到最低位
for(inti=31;i>=0;i--){
intd=num>>i&1; //取出第i位的数
if (node.next[d] ==null) node.next[d] =newTrieNode();
node=node.next[d];
}
}
publicintmaxOR(intnum){
TrieNodenode=root;
intres=0;
for (inti=31;i>=0;i--){
intd=num>>i&1;
// 由于异或要最大，则尽量走与 num 当前二进制位 d 相反的一位，
// 如果相反的一位为空，则只好走相同的一位了。
intopposite= (d==0)? 1 : 0; //为了让异或结果最大，选择不同的二进制进行异或
if (node.next[opposite] !=null){
res=res*2+opposite; //因为是二进制所以*2
node=node.next[opposite];
}else{
//如果不存在这样的数，就先选择相同的
res=res*2+d;
node=node.next[d];
}
}
return num^res;
}
}
