題目：

解析：這個題目的關(guān)鍵問題是“最短的編碼”，這里可以知道應該是Huffman編碼了。

哈夫曼編碼是一種可變字長編碼，也就是說對于不同的字符的編碼不是定長的，所以才能比定長編碼要短。

?

哈夫曼樹

哈夫曼編碼依靠的就是哈夫曼樹，根據(jù)每個字符出現(xiàn)的次數(shù)作為權(quán)重，生成對應的哈夫曼樹，對應的編碼長度即為最短。

哈夫曼樹的構(gòu)造很簡單，每次從所有的權(quán)重中選出最小兩個分別作為的作為子節(jié)點（一般左節(jié)點權(quán)重小于右節(jié)點），權(quán)重相加值為父節(jié)點權(quán)重，再把父節(jié)點代替兩個子節(jié)點重新進入隊列中，不斷循環(huán)最后會得到一顆二叉樹。

例子：以2,4,5,8,13為權(quán)構(gòu)造哈夫曼樹

① 選出最小兩個數(shù)為2和4，以2為左節(jié)點，4為右節(jié)點構(gòu)造二叉樹，和為父節(jié)點的值，并且將父節(jié)點的權(quán)放回

完成后權(quán)值為：5,6,8,13

② 選出最小兩個數(shù)5和6，操作同上

權(quán)值為：8,11,13

③ 選出8和11，操作同上

權(quán)值為：13,19

④ 最后剩下兩個，分別作為左右節(jié)點

得到的二叉樹就是哈夫曼樹。

回到哈夫曼編碼，哈夫曼編碼對應的就是將每個字符出現(xiàn)的次數(shù)作為權(quán)，生成對應的哈夫曼樹，然后以左子樹為0，右子樹為1，對每個字符進行編碼。

所以對于題目中的例子，生成的哈夫曼樹和對應的編碼應該是這樣的：

注意：二叉樹的構(gòu)造不一定相同，因為部子節(jié)點的權(quán)是相同的，構(gòu)造的二叉樹會有所不同。

?

代碼：

① 定義哈夫曼樹節(jié)點：

1 public class Node { 2 Character value; // 節(jié)點字符 3 int count = 1; // 深度（節(jié)點與根節(jié)點的距離） 4 int power = 1; // 權(quán)（出現(xiàn)次數(shù)） 5 Node left = null; // 左子節(jié)點 6 Node right = null; // 右子節(jié)點 7 8 /** 9 * 更新子節(jié)點的深度 10 */ 11 public void notifyChild() { 12 count += 1; 13 if (left != null) { 14 left.notifyChild(); 15 } 16 if (right != null) { 17 right.notifyChild(); 18 } 19 } 20 21 public Node(Character value) { 22 this.value = value; 23 } 24 25 public boolean sameValue(char c) { 26 return c == value; 27 } 28 29 /** 30 * 根據(jù)傳入的節(jié)點作為此節(jié)點的子節(jié)點 31 * @param left 左節(jié)點 32 * @param right 右節(jié)點 33 */ 34 public void updateChild(Node left, Node right) { 35 this.left = left; 36 this.right = right; 37 this.power = left.power + right.power; 38 } 39 40 }

11-19行為更新操作，因為最后要得到每個字符的編碼長度，這個長度實際上是在構(gòu)造二叉樹的時候可以確定的，因為如果父節(jié)點被選出，則其子節(jié)點的深度會增加1，這個方法用來通知子節(jié)點進行深度加一操作。

② 編寫計算方法

1 void count(String s){ 2 // 計算每個字符出現(xiàn)的次數(shù) 3 ArrayList<Node> chars = new ArrayList<>(); 4 char[] StrChars = s.toCharArray(); 5 chars.add(new Node(StrChars[0])); 6 for (int j = 1; j < StrChars.length; j++) { 7 char c = StrChars[j]; 8 int size = chars.size(); 9 for (int i = 0; i < size; i++) { 10 if (chars.get(i).sameValue(c)) { 11 chars.get(i).power += 1; 12 break; 13 } 14 if (i == size - 1) { 15 chars.add(new Node(c)); 16 } 17 } 18 } 19 20 // 根據(jù)權(quán)值排序，從小到大，插入排序 21 ArrayList<Node> nodes = new ArrayList<>(); 22 nodes.add(chars.get(0)); 23 for (int i = 1; i < chars.size(); i++) { 24 int size = nodes.size(); 25 for (int j = 0; j < size; j++) { 26 Node c = chars.get(i); 27 if (c.power < nodes.get(j).power) { 28 nodes.add(j, c); 29 break; 30 } 31 if (j == size - 1) { 32 nodes.add(c); 33 } 34 } 35 } 36 chars = nodes; 37 38 // 構(gòu)造哈夫曼樹 39 while (chars.size() > 1) { 40 Node root = new Node(null); 41 Node left = chars.get(0); 42 Node right = chars.get(1); 43 root.updateChild(left, right); // 生成新節(jié)點 44 chars.remove(0); // 刪除被選節(jié)點 45 chars.remove(0); // 刪除被選節(jié)點 46 int size = chars.size(); 47 if (size == 0) { 48 chars.add(root); // 退出循環(huán)條件 49 } 50 for (int i = 0; i < size; i++) { 51 if (root.power < chars.get(i).power) { 52 chars.add(i, root); // 將新生成的節(jié)點插入到對應位置使得序列依然有序 53 root.notifyChild(); // 通知子節(jié)點更新深度 54 break; 55 } 56 if (i == size - 1) { 57 chars.add(root); 58 root.notifyChild(); 59 } 60 } 61 } 62 63 // 遍歷二叉樹，計算最短編碼長度 64 int sum = 0; 65 Stack<Node> stack = new Stack<>(); 66 Node root = chars.get(0); 67 stack.add(root); 68 while (!stack.isEmpty()) { 69 root = stack.pop(); 70 if (root.value != null) { 71 sum += root.power * root.count; 72 } 73 if (root.right != null) { 74 stack.push(root.right); 75 } 76 if (root.left != null) { 77 stack.push(root.left); 78 } 79 } 80 System.out.println(sum); 81 }

注意：

① 這里排序使用了插入排序，時間復雜度較高，但是通過面試題是沒問題的，考慮到sort方法不能用，就只能折中了。

② 這里的節(jié)點的深度是指子節(jié)點到根節(jié)點的距離，如例子中E到根節(jié)點距離為2

③ 深度的計算只有字符節(jié)點是正確的，因為方法中不加判斷的對根節(jié)點和子節(jié)點都加一了，但是計算只要求子節(jié)點，所以忽略這個問題。

?

完整代碼如下：

1 package com.fndroid; 2 3 import java.util.*; 4 5 public class Main { 6 7 public static void main(String[] args) { 8 Main solution = new Main(); 9 Scanner scanner = new Scanner(System.in); 10 while (scanner.hasNext()) { 11 solution.count(scanner.next()); 12 } 13 } 14 15 void count(String s){ 16 // 計算每個字符出現(xiàn)的次數(shù) 17 ArrayList<Node> chars = new ArrayList<>(); 18 char[] StrChars = s.toCharArray(); 19 chars.add(new Node(StrChars[0])); 20 for (int j = 1; j < StrChars.length; j++) { 21 char c = StrChars[j]; 22 int size = chars.size(); 23 for (int i = 0; i < size; i++) { 24 if (chars.get(i).sameValue(c)) { 25 chars.get(i).power += 1; 26 break; 27 } 28 if (i == size - 1) { 29 chars.add(new Node(c)); 30 } 31 } 32 } 33 34 // 根據(jù)權(quán)值排序，從小到大，插入排序 35 ArrayList<Node> nodes = new ArrayList<>(); 36 nodes.add(chars.get(0)); 37 for (int i = 1; i < chars.size(); i++) { 38 int size = nodes.size(); 39 for (int j = 0; j < size; j++) { 40 Node c = chars.get(i); 41 if (c.power < nodes.get(j).power) { 42 nodes.add(j, c); 43 break; 44 } 45 if (j == size - 1) { 46 nodes.add(c); 47 } 48 } 49 } 50 chars = nodes; 51 52 // 構(gòu)造哈夫曼樹 53 while (chars.size() > 1) { 54 Node root = new Node(null); 55 Node left = chars.get(0); 56 Node right = chars.get(1); 57 root.updateChild(left, right); // 生成新節(jié)點 58 chars.remove(0); // 刪除被選節(jié)點 59 chars.remove(0); // 刪除被選節(jié)點 60 int size = chars.size(); 61 if (size == 0) { 62 chars.add(root); // 退出循環(huán)條件 63 } 64 for (int i = 0; i < size; i++) { 65 if (root.power < chars.get(i).power) { 66 chars.add(i, root); // 將新生成的節(jié)點插入到對應位置使得序列依然有序 67 root.notifyChild(); // 通知子節(jié)點更新深度 68 break; 69 } 70 if (i == size - 1) { 71 chars.add(root); 72 root.notifyChild(); 73 } 74 } 75 } 76 77 // 遍歷二叉樹，計算最短編碼長度 78 int sum = 0; 79 Stack<Node> stack = new Stack<>(); 80 Node root = chars.get(0); 81 stack.add(root); 82 while (!stack.isEmpty()) { 83 root = stack.pop(); 84 if (root.value != null) { 85 sum += root.power * root.count; 86 } 87 if (root.right != null) { 88 stack.push(root.right); 89 } 90 if (root.left != null) { 91 stack.push(root.left); 92 } 93 } 94 System.out.println(sum); 95 } 96 97 public class Node { 98 Character value; // 節(jié)點字符 99 int count = 1; // 深度（節(jié)點與根節(jié)點的距離） 100 int power = 1; // 權(quán)（出現(xiàn)次數(shù)） 101 Node left = null; // 左子節(jié)點 102 Node right = null; // 右子節(jié)點 103 104 /** 105 * 更新子節(jié)點的深度 106 */ 107 public void notifyChild() { 108 count += 1; 109 if (left != null) { 110 left.notifyChild(); 111 } 112 if (right != null) { 113 right.notifyChild(); 114 } 115 } 116 117 public Node(Character value) { 118 this.value = value; 119 } 120 121 public boolean sameValue(char c) { 122 return c == value; 123 } 124 125 /** 126 * 根據(jù)傳入的節(jié)點作為此節(jié)點的子節(jié)點 127 * @param left 左節(jié)點 128 * @param right 右節(jié)點 129 */ 130 public void updateChild(Node left, Node right) { 131 this.left = left; 132 this.right = right; 133 this.power = left.power + right.power; 134 } 135 136 } 137 } 完整代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/Fndroid/p/6254187.html

總結(jié)

以上是生活随笔為你收集整理的算法面试题-美团点评2016研发工程师编程题(二)-字符编码（哈夫曼树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。