poj-1521

282MS Java

import java.util.Collections;  import java.util.List;   import java.util.ArrayList;  import java.util.Scanner;  import java.util.Comparator;  import java.util.Arrays;  public class Main { private static final int MAX = 27; private static final char UNDER_SCORE = '_'; private class CharacterComparator implements Comparator<CharacterTreeNode> { @Override    public int compare(CharacterTreeNode o1, CharacterTreeNode o2) {        return o1.num - o2.num;    } } private CharacterComparator mComparator; private int[] mCharacterMap; private int mStrLength; // private class Character { // public char content; // public int num; // public boolean isParentNode; // } private class CharacterTreeNode { public CharacterTreeNode left; public CharacterTreeNode right; public int num; public char content ; }; private int mCharType; private CharacterTreeNode[] mCharacterInfo; public void preProcess(String str) { for (int i = 0; i < MAX; i++) { mCharacterInfo[i] = new CharacterTreeNode(); mCharacterInfo[i].left = null; mCharacterInfo[i].right = null; } mStrLength = str.length(); for (int i = 0; i < MAX; i++) { mCharacterMap[i] = 0;   } byte[] byteArray = str.getBytes(); for (int i = 0; i < mStrLength; i++) { if (byteArray[i] == UNDER_SCORE) { mCharacterMap[MAX-1]++; } else { mCharacterMap[byteArray[i]-'A']++; } } for (int i = 0; i < MAX-1; i++) { if (mCharacterMap[i] != 0) { // this char appear mCharacterInfo[mCharType].content = (char)(i + 'A'); mCharacterInfo[mCharType++].num = mCharacterMap[i]; }   } if (mCharacterMap[MAX-1] != 0) { mCharacterInfo[mCharType].content = '_'; mCharacterInfo[mCharType++].num = mCharacterMap[MAX-1]; } } private int mOptinalLength; public void bypassTree(CharacterTreeNode node, int degree) { if (node == null) { return; } if (node.left == null && node.right == null) { // System.out.println(node.content + " " + degree); mOptinalLength += (degree-1)*(node.num); } else { bypassTree(node.left, degree + 1); bypassTree(node.right, degree + 1); } } public void solve(String str) { mOptinalLength = 0; mCharType = 0; preProcess(str); int treeNodeNum = mCharType; while(treeNodeNum > 1) { Arrays.sort(mCharacterInfo, 0, treeNodeNum, mComparator); CharacterTreeNode leftTreeNode = mCharacterInfo[0]; CharacterTreeNode rightTreeNode = mCharacterInfo[1]; CharacterTreeNode sumTreeNode = new CharacterTreeNode(); sumTreeNode.num = leftTreeNode.num + rightTreeNode.num; sumTreeNode.left = leftTreeNode.num < rightTreeNode.num ?  leftTreeNode : rightTreeNode; sumTreeNode.right = leftTreeNode.num >= rightTreeNode.num ?  leftTreeNode : rightTreeNode; mCharacterInfo[0] = sumTreeNode; if (treeNodeNum > 2) { mCharacterInfo[1] = mCharacterInfo[treeNodeNum-1]; } treeNodeNum--; } bypassTree(mCharacterInfo[0], 1); int orginalLength = mStrLength * 8; if (mCharType == 1) { mOptinalLength = mStrLength; } // java.text.DecimalFormat df = new java.text.DecimalFormat("#.#"); String result = String.format("%.1f", (double)orginalLength/mOptinalLength); // System.out.println(orginalLength + " " + mOptinalLength + " " + ((int)(((double)orginalLength)/mOptinalLength*10))/10.0); System.out.println(orginalLength + " " + mOptinalLength + " " + result); } public Main() { mCharType = 0; mOptinalLength = 0; mCharacterInfo = new CharacterTreeNode[MAX]; for (int i = 0; i < MAX; i++) { mCharacterInfo[i] = new CharacterTreeNode(); mCharacterInfo[i].left = null; mCharacterInfo[i].right = null; } mComparator = new CharacterComparator(); mCharacterMap = new int[MAX]; } public static void main(String[] args) { Main solver = new Main(); Scanner input = new Scanner(System.in); while(true) { String str = input.next(); if (str.equals("END")) { return; } solver.solve(str); } } }

282MS Java

纯哈弗曼树水题，复习如何构建哈弗曼树。

两个注意：

1： 注意只有一个字母，哈弗曼树不适用

2： java一定要注意，题目虽然没说四舍五入，但实际上是要求四舍五入，WA已经好几次了...

没有优先队列，为了继续训练java的基本操作，每次合并前两个节点，第一个节点更新为合并节点，第二个节点和

队列的最后一个节点交换(java全引用好，直接指过去，如果只有两个节点，就不用了)，下次重新排序，但范围-1. 直到最后只剩下一个节点退出。

在每个叶节点（每个编码字符）计算树高和数量的乘积，并积累最后一次遍历形成的树。

mark，然后写一个版本的优先队列.