64 条题解
-
0
chengrui LV 10 @ 2009-10-06 16:00:42
编译通过...
├ 测试数据 01：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
第282个
以前以为很难......
没想到是哈夫曼树......水~~~ -
0
yzl609271536 LV 10 @ 2009-10-06 14:41:38
编译通过...
├ 测试数据 01：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms很水 但是堆竟然调了一些时间
-
0
luoruotian LV 8 @ 2009-09-26 11:18:34
为什么，我的程序老师通不过啊，连原字符串长度的8倍都是错的，真奇怪
-
0
chen199277 LV 10 @ 2009-08-25 10:50:53
虽然楼下有说过，
还是忍不住提醒一下：
一定要考虑当字符串为一个相同字符时！！！还有，如果有谁知道哈弗曼数的正确性证明。
拜托+QQ1003545371 -
0
只要编码满足任意两个i j i的编码不是j的编码的前缀就行，于是考虑构造一棵trie满足节点是01，且每个叶子都对应了一个字母，且根到叶子的距离和*对应单词权最小..
接下来考虑每一棵可行的树，实际上等于N棵只有一个叶子节点且树权为单词权的树，按照下面规则合并得到，规则是：
1：由给定的n个权值构造n棵树只有一个叶子结点的二叉树，得到一个二叉树的合F； 2：再F中选取二棵二叉树作为左，右子树构造一棵新的二叉树，这棵树的根结点的权值为左右子树根结点权值之和。 3：在集合F中删除作为左右子树的二棵二叉树，并将新建的二叉树加入到集合F中。 4：重复2 ,3两步，当F中只剩下一棵二叉树时，结束
可以看出，如果能找到使得最后代价最小的合并顺序，那么就他就一定是答案，可以发现最小的合并顺序求法就是合并果子，结束。 -
0
EZ_ray040123 LV 10 @ 2009-08-04 18:16:35
lsss
为什么要保证任一个字符的编码不为另一字符的前缀？
保证任意某k1个编码不等于任意某k2个编码的排列不就可以了吗？
如 AB
A:10
B:100
10100 难道不唯一 -
0
zhengfangyi LV 10 @ 2009-07-27 12:51:49
一定要特判一下只有1种字母的情况！！！！
就为这个交了3次。
-
0
pRoevollove LV 9 @ 2009-03-12 21:13:02
可是还是不怎么懂haffman编码
chengrui
LV 10
@ 2009-10-06 16:00:42
