转换哈夫曼编码问题

x33g5p2x  于10天前 转载在 其他  
字(1.4k)|赞(0)|评价(0)|浏览(13)

一 原题链接

Inverting Huffman - UVA 12676 - Virtual Judge

https://vjudge.net/problem/UVA-12676

二 输入和输出

输入样例

2

1 1

4

2 2 2 2

10

8 2 4 7 5 1 6 9 3 9
输出样例

2

4

89

三 算法设计

本问题不是简单的哈夫曼编码问题,而是反其道而行之,根据编码长度,推测最小字符数。

例如
4 // 表 4 个不同字符

3 1 2 3 // 每个字符编码长度

其最长编码为3,即深度为3.底层节点权值至少为1,每一层节点的权值至少是下一层节点权值的最大值。如果当前节点的权值比下一层节点权值小,就会出现在下一层了,因为权值越小,出现的层次越大,如下图所示。

1 在每一层都用一个深度数组 deep[] 记录该层节点的权值,将该层每个节点的权值都初始化为0,等待推测权值。
2 根据输入的编码长度算出最大长度,即哈夫曼树的最大深度 maxd。

3 从最大深度 maxd 向上计算并推测,直到树根。开始时 temp =1。

  • i = maxd:第 i 层节点权值如果为0,则被初始为 temp。对第 i 层从小到大排序,然后将第i 层每两个合并,将权值放入上一层(i-1层)。更新 temp 为第 i 层排序后最后一个元素(最大元素)。
  • i = max-1:重复上述操作。
  • i = 0:结束,输出0层第1个元素。

四 实现

package tree;

import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;

public class UVA12676 {
    public static void main(String[] args) {
        final int maxn = 55;
        Vector<Long> deep[] = new Vector[maxn];
        for (int i = 0; i < deep.length; i++) {
            deep[i] = new Vector<>();
        }
        int x;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++)
                deep[i].clear();
            int maxd = 0;
            for (int i = 0; i < n; i++) {
                x = scanner.nextInt();
                deep[x].addElement(0L);
                maxd = Math.max(maxd, x); // 求最大深度
            }
            long temp = 1;
            for (int i = maxd; i > 0; i--) {
                for (int j = 0; j < deep[i].size(); j++) {
                    if (deep[i].get(j) == 0)
                        deep[i].set(j, temp); // 将第i层最大的元素值赋值给 i-1 层没有权值的结点
                }
                Collections.sort(deep[i]); // 第i层排序

                for (int j = 0; j < deep[i].size(); j += 2)
                    deep[i - 1].addElement(deep[i].get(j) + deep[i].get(j + 1)); //合并后放入上一层
                temp = deep[i].get(deep[i].size() - 1); // 取第 i 层的最后一个元素,即第 i 层最大的元素
            }
            System.out.println(deep[0].get(0)); // 输出树根的权值
        }
    }
}

五 测试

绿色为输入,白色为输出

相关文章