首先定義一個TreeNode:
static class TreeNode {
int weight;//權重，出現次數
Character ch;//如果是初始字符，則ch為字符，如果是合并的，則為null
TreeNode left;
TreeNode right;
public TreeNode(int weight) {
this.weight = weight;
}
public TreeNode(int weight, Character ch) {
this.weight = weight;
this.ch = ch;
}
}
之后定義一個優先佇列，以TreeNode中weight比較，建立小頂綴，已確認每次都取最小值：
Queue<TreeNode> queue=new PriorityQueue<>(hs.size(), new Comparator<TreeNode>() {
@Override
public int compare(TreeNode o1, TreeNode o2) {
return Integer.compare(o1.weight,o2.weight);
}
});
HashMap統計每個字符個數，以個數頻率確認最少的字符，之后佇列中先取建立哈夫曼樹，
char[] chars = s.toCharArray();
HashMap<Character,Integer> hs=new HashMap<>();
for(int i=0;i<chars.length;i++){
if(hs.containsKey(chars[i])){
hs.put(chars[i],hs.get(chars[i])+1);
}
else {
hs.put(chars[i],1);
}
}
將hashmap中的key，value放入queue;
for(Map.Entry<Character,Integer> a:hs.entrySet()){
queue.offer(new TreeNode(a.getValue(),a.getKey()));
}
queue出兩個，建立一個父類TreeNode，放入queue，直到剩root;
while (queue.size()>1){
TreeNode left = queue.poll();
TreeNode right = queue.poll();
TreeNode father=new TreeNode(left.weight+right.weight);
father.left = left;
father.right = right;
queue.offer(father);
}
TreeNode root=queue.poll();
計算最少編碼數count
public static int getcount(TreeNode node,int depth){
if(node==null){
return 0;
}
else {
return (node.ch==null?0:node.weight)*depth+getcount(node.right,depth+1)+getcount(node.left,depth+1);
}
}
ok，就這樣，自己組裝叭，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/5831.html
標籤：其他
上一篇：AT2362 [AGC012B] Splatter Painting（思維、dfs染色、剪枝）
下一篇：21屆秋招快手前端面經