流利说编程题

想不到哈弗曼树居然写不出来啊啊啊啊啊
后来自己捋一捋,理清思路写出来了。。

import java.util.*;

public class EncodeString {

    static class HuffmanNode implements Comparable<HuffmanNode> {

        char value;

        int frequence;

        HuffmanNode left;

        HuffmanNode right;

        HuffmanNode(char value, int frequence) {
            this.value = value;
            this.frequence = frequence;
        }

        HuffmanNode(char value, int frequence, HuffmanNode left, HuffmanNode right) {
            this.value = value;
            this.frequence = frequence;
            this.left = left;
            this.right = right;
        }

        public int compareTo(HuffmanNode o) {
            return this.frequence - o.frequence;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }
    }

    public static String huffmanTree(String s) {
        int len = s.length();
        //根据明文先构建树,才可以压缩

        //计算频率
        HashMap<Character,Integer> frequences = new HashMap<>();
        char[] input = s.toCharArray();
        for (int i = 0; i < input.length; i++) {
            if (frequences.containsKey(input[i]))
                frequences.put(input[i],frequences.get(input[i]) + 1);
            else
                frequences.put(input[i],1);
        }

        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();//暂时保存子树
        //初始化多个树
        for (Character word: frequences.keySet()) {
            HuffmanNode node = new HuffmanNode(word, frequences.get(word));
            pq.add(node);
        }
        //开始创建
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode parent = new HuffmanNode('\0', left.frequence + right.frequence, left, right);
            pq.add(parent);
        }
        HuffmanNode root = pq.poll();

        //计算编码
        HashMap<Character,String> codes = new HashMap<>();
        initCodes(root, "",codes);

        return compress(input,codes);
    }

    public static String compress(char[] input,HashMap<Character,String> codes) {
        String output = "";
        for (int i = 0; i < input.length; i++) {
            String code = codes.get(input[i]);
            output += code;
        }
        return output;
    }

    private static void initCodes(HuffmanNode node, String s,HashMap<Character,String> map) {
        if (node.isLeaf()) {
            map.put(node.value,s);
            return;
        }
        initCodes(node.left, s + '0',map);
        initCodes(node.right, s + '1',map);
    }

    public static void main(String[] args) {
        System.out.println(huffmanTree("liulishuo").length());

    }

}
#笔试题目##流利说#
全部评论
利用规律做就好了,你这样麻烦了
点赞 回复 分享
发布于 2019-07-31 00:02

相关推荐

码农索隆:竞争压力小,就你一个不用卷
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
Gaynes:查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务