1.前綴樹（Trie Tree）

1.1 字符串生成前綴樹的過程

字母是填在路上的，不是填在節點上的。

首先是一個空的頭結點：

加入“abc”到這棵樹中：

頭結點有到a的路嗎？沒有，添加：

有a到b的路嗎？沒有，添加，c也一樣：

接著添加字符串“bce”：

添加字符串“abd”：

添加字符串“bef”：

在添加N個字符串之后，可以查詢，“某個字符串是否是以“be”開始的”。

若要查詢“是否含有字符串“be”？”，原始的樹結構，不足以實現這個功能。

• 添加了“bef”，但是“be”的路徑和“bef”的路徑是重合的，無法判斷有沒有加過“be”。

需在節點處添加一個值，表示有多少個字符串是以這個字符結尾的。更改之后的樹結構如下圖：

此時b-e中e后面的節點值為0，說明沒有加過"be"。

此樹結構還可以查某個字符串加過幾次。

“給出有多少個字符串以給定的額字符串作為前綴”——需要再加一個數據項：每一個節點被劃過了多少次。

上述樹結構，更改之后如下圖所示：

添加字符串的代價：字符串本身的長度，和數據量N無關；

查某個字符的代價：字符串本身的長度，和數據量N無關；

1.2 代碼實現

package Tree;public class TrieTree {public static void main(String[] args) {Trie trie = new Trie();System.out.println(trie.search("hello"));trie.insert("hello");System.out.println(trie.search("hello"));trie.delete("hello");System.out.println(trie.search("hello"));trie.insert("hello");trie.insert("hello");trie.delete("hello");System.out.println(trie.search("hello"));trie.delete("hello");System.out.println(trie.search("hello"));trie.insert("helloa");trie.insert("helloac");trie.insert("helloab");trie.insert("helload");trie.delete("helloa");System.out.println(trie.search("helloa"));System.out.println(trie.prefixNumber("hello"));}public static class TrieNode{public int path;public int end;public TrieNode[] nexts;//此節點有多少條通往下層的路//通過判斷此節點的路徑指向的節點是否為空來判斷這條路是否存在public TrieNode() {this.path=0;this.end=0;this.nexts=new TrieNode[26];//26個字母就26條路}}public static class Trie{TrieNode root;public Trie() {root=new TrieNode();}public void insert(String str) {if(str==null)return;char[] arr=str.toCharArray();TrieNode node=root;int index=0;for(int i=0;i<arr.length;i++) {index=arr[i]-'a';//0~25if(node.nexts[index]==null)node.nexts[index]=new TrieNode();node=node.nexts[index];//node往下挑跳一個，i=0時是從頭結點跳到第一個節點node.path++;}node.end++;//整個字符串加完之后，最后一個字符的end+1；}public int search(String str) {if(str==null)return 0;char[] arr=str.toCharArray();TrieNode node=root;int index=0;for(int i=0;i<arr.length;i++) {index=arr[i]-'a';//0~25if(node.nexts[index]!=null)node=node.nexts[index];elsereturn 0;}return node.end;}public void delete(String str) {if(search(str)==0)return;char[] arr=str.toCharArray();TrieNode node=root;int index=0;for(int i=0;i<arr.length;i++) {index=arr[i]-'a';//0~25if(--node.nexts[index].path==0) {//判斷是否需要斷掉這條路node.nexts[index]=null;return;}elsenode=node.nexts[index];}node.end--;}public int prefixNumber(String str) {if(str==null)return 0;char[] arr=str.toCharArray();TrieNode node=root;int index=0;for(int i=0;i<arr.length;i++) {index=arr[i]-'a';//0~25if(node.nexts[index]!=null)node=node.nexts[index];elsereturn 0;}return node.path;}} }

運行結果：

2.貪心策略

（使用對數器嚴重貪心策略是否正確，不要糾結正確性證明）

貪心：根據某個標準分出個優先級，然后按照優先級的順序執行。

2.1 舉例

拼接字符串，使得結果為最小（按字典序）。

比如："ab"、“cd”、"ef"三個字符串，拼接的結果可以由多種，但是”abcdef“這個結果才是最小的，題目中想要的。

2.1.1 分析

若先將字符串數組中的字符串拍好序再進行拼接，如下：

if(str1<=str2)str1連接str2; elsestr2連接str1;

這種方式不對，因為："b"<"ba"，但是拼接之后"bba">"bab"。

所以正確的比較策略應該是：

if(str1連接str2<=str2連接str1)str1放前面; elsestr2放前面;

即，誰作為前綴更小誰放前面。

2.1.2 代碼實現

package Solution;import java.util.Arrays; import java.util.Comparator;public class StrCon {public static void main(String[] args) {String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };System.out.println(lowestString(strs1));String[] strs2 = { "ba", "b" };System.out.println(lowestString(strs2));}public static class MyComparator implements Comparator<String>{@Overridepublic int compare(String str1, String str2) {return (str1+str2).compareTo(str2+str1);/** compareTo* 如果指定的數與參數相等返回0。* 如果指定的數小于參數返回 -1。* 如果指定的數大于參數返回 1。*/} }public static String lowestString(String[] strs) {if(strs==null||strs.length==0)return " ";Arrays.sort(strs, new MyComparator());String res=" ";for(int i=0;i<strs.length;i++) res+=strs[i];return res;} }

運行結果：

2.1.3 結論

當比較策略是個環時，不具有傳遞性，這個比較策略無效。

例如，有甲、乙、丙三個變量，訂制的策略為：

• 甲和乙：甲在前；
• 乙和丙：乙在前；
• 甲和丙：丙在前。

以上策略構成一個環。

要使得比較的結果唯一，則設定的比較策略要具有傳遞性，即：

• a.b≤b.a
• b.c≤c.b
• 則：a.c≤c.a

以上式子中，將字符串等同于k進制的數：

• 連接的結果為：
• 即12乘以10（進制）的21長度（2）次方

則字符串拼接可以理解為：

令，則上述的傳遞性規則可表示為：

化簡：

由以上兩個式子得：

由數的交換律和結合律可知：

所以：

化簡結果：

得證。

要證明得到的字符串s是最小的字典序，即證明任意交換兩個字符，得到的字典序都比s的字典序大。，

以得到的最小字典序字符串結果為：，要證明肯定大于等于

在第一個串中，在的前面，則：

若將和交換：

一直換到和挨著：

然后將b往前換：

最終：

所以，得到的結果已是最小。

總結

以上是生活随笔為你收集整理的算法练习day13——190401（前缀树、贪心策略拼接字符串使字典序最小）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。