首页 > 试题广场 >

字符编码

[编程题]字符编码

热度指数：5688 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请设计一个算法，给一个字符串进行二进制编码（哈夫曼编码），使得编码后字符串的长度最短。

数据范围：字符串长度满足 $1 < n \le 1000 \$ ，本题有多组输入

输入描述:

每组数据一行，为待编码的字符串。保证字符串长度小于等于1000。

输出描述:

一行输出最短的编码后长度。

示例1

输入

MT-TECH-TEAM

输出

算法知识视频讲解

Java

牛客35031561号

哈夫曼编码：1.按照字符词频建立小根堆。2. 每次找2个出现次数最少的字符，统计出现次数（对于其当前编码长度），再将两字符词频相加作为新字符的词频放入小根堆，直到小根堆中不足2个元素，结束。
假如，字符a和字符b的词频出现次数最少，其编码后缀为0和1，把‘ab’作为新字符加入小根堆，按照此过程可以得到‘ab’的编码（假如为111），则字符a和字符b的完成编码为‘1110’ 和‘1111’。

import java.util.*;
public class  Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            char[] ch = sc.next().toCharArray();
            Map map = new HashMap();
            for(int i=0; i < ch.length; i++) 
                map.put(ch[i], map.getOrDefault(ch[i], 0) + 1);
            PriorityQueue q = new PriorityQueue();
            for(int value : map.values())
                q.offer(value);
            int res = 0;
            while(q.size() >= 2) {
                int a = q.poll(), b = q.poll();
                res += a + b;
                q.offer(a+b);
            }
            System.out.println(res);
        }
    }
}

编辑于 2020-07-01 18:14:24 回复(0)

Java

.zZZ~~

package NewCoder.XiaoZhaoZhenTi;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
public class test3_7 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			map2.clear();
			String string = scanner.nextLine();
			char[] chars = string.toCharArray();
			Map<String,Integer>  mapx = new HashMap<>();
			for(int i = 0 ; i < chars.length ; i ++){
				String temp = String.valueOf(chars[i]);
				if(mapx.containsKey(temp)){
					mapx.put(temp,mapx.get(temp)+1);
				}else{
					mapx.put(temp, 1);
				}
			}
			ArrayList<Integer> numList1 = new ArrayList<>();
			Iterator<Entry<String, Integer>> iterator = mapx.entrySet().iterator();
			while(iterator.hasNext()){
				Integer xInteger = iterator.next().getValue();
				numList1.add(xInteger);
			}
			Collections.sort(numList1);
			//对数字排序一次，方便以后找两个最小值
			ArrayList<TreeNode> numList = new ArrayList<>();
			for(int i = 0 ; i < numList1.size() ; i ++){
				numList.add(new TreeNode(numList1.get(i)));	
				//得到所有字符出现次数的树节点
			}
			if(numList.size()<=2){
				System.out.println(numList.size());
				continue;
			}
			Set<TreeNode> set = new HashSet<>();
			TreeNode root = null;
			//构建哈夫曼树
			while(numList.size() !=1){
				TreeNode xNode = numList.remove(0);//当前最小的
				TreeNode yNode = numList.remove(0);//当前第二小
				TreeNode sumNode = new TreeNode(xNode.value+yNode.value);
				int isadd = 0;
				for(int i = 0 ; i < numList.size() ; i++){
					if(numList.get(i).value > sumNode.value){
						numList.add(i, sumNode); 
						//把新合并的节点插到list里,注意保持递增顺序
						isadd = 1;
						break;
					}
				}
				if(isadd == 0){
					numList.add(sumNode);
				}
				set.add(sumNode);
				sumNode.left = xNode;
				sumNode.right = yNode;
				root = sumNode; //构建新节点的左右子节点
			}
			fun(root, 0); //计算所有的叶子结点的深度
			Iterator<Entry<TreeNode, Integer>> iterator2 = map2.entrySet().iterator();
			int result = 0;
			while(iterator2.hasNext()){
				Entry<TreeNode, Integer> entry = iterator2.next();
				result += entry.getKey().value*entry.getValue();//所有叶子结点深度*值 之和
			}
			System.out.println(result);
			
		}
	}
	static Map<TreeNode, Integer> map2 = new HashMap<>();
	//计算所有的叶子结点的深度
	static void fun(TreeNode root,int length){
		if(root.left == null && root.right == null){
			map2.put(root, length);
			return;
		}else{
			if(root.left!=null){
				fun(root.left, length+1);
			}
			if(root.right!=null){
				fun(root.right, length+1);
			}
		}
	}
}
class TreeNode{
	int value ;
	TreeNode left = null;
	TreeNode right =  null;
	public TreeNode(int value) {
		super();
		this.value = value;
	}
	public TreeNode getLeft() {
		return left;
	}
	public void setLeft(TreeNode left) {
		this.left = left;
	}
	public TreeNode getRight() {
		return right;
	}
	public void setRight(TreeNode right) {
		this.right = right;
	}
}

发表于 2017-05-16 22:13:25 回复(0)

Java

猫时雨

1.将字符串转为字符数组，遍历统计每个字符出现的次数，放入hash表中

2.创建节点TreeNode，放入一个优先队列

3.构建哈夫曼树合并两个权重最小的节点，直到只剩下根节点root

4.带着深度遍历树，计算长度和

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String s = input.nextLine();
            int result = hafuman(s);
            System.out.println(result);
        }
    }

    public static int hafuman(String s) {
        char[] chars = s.toCharArray();
        //hash表存放每个字符和出现的次数
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (hash.containsKey(chars[i])) {
                hash.put(chars[i], hash.get(chars[i]) + 1);
            } else {
                hash.put(chars[i], 1);
            }
        }
        //优先队列（最小推），每次能得到weigh最小的node
        Queue<TreeNode> q = new PriorityQueue<>(hash.size(), new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return Integer.compare(o1.weight, o2.weight);
            }
        });
        for (Map.Entry<Character, Integer> entry : hash.entrySet()) {
            q.offer(new TreeNode(entry.getValue(), entry.getKey()));
        }
        while (q.size() > 1) {
            //弹出两个最小的，合并为一个node
            TreeNode left = q.poll();
            TreeNode right = q.poll();
            TreeNode father = new TreeNode(left.weight + right.weight);
            father.left = left;
            father.right = right;
            q.offer(father);
        }
        TreeNode root = q.poll();
        //计算长度      
      	return valLength(root, 0);
    }

    public static int valLength(TreeNode node, int depth) {
        if (node == null) return 0;//仅计算ch有值的
        return (node.ch == null ? 0 : node.weight) * depth + valLength(node.left, depth + 1) + valLength(node.right, depth + 1);
    }

    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;
        }
    }
}

编辑于 2016-09-04 21:07:01 回复(4)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String s = sc.nextLine();
			Map<Character, Integer> map = new HashMap<>();
			for (int i = 0; i < s.length(); i ++) {
				char key = s.charAt(i);
				map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
			}
			PriorityQueue<Node> queue = new PriorityQueue<>();
			for (Character c:map.keySet()) {
				queue.add(new Node(map.get(c)));
			}
			Node root = null;
			while (queue.size() != 1) {
				Node left = queue.poll();
				Node right = queue.poll();
				root = new Node(left.value + right.value);
				root.left = left;
				root.right = right;
				queue.add(root);
			}
			System.out.println(countLength(root, 0));
		}
	}

	public static int countLength(Node root, int level) {
		if(root.left == null && root.right == null) return root.value * level;
		return countLength(root.left, level + 1) + countLength(root.right, level + 1);
	}

	static class Node implements Comparable<Node> {
		private int value;
		private Node left;
		private Node right;

		public Node(int value) {
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
}

编辑于 2017-04-05 17:23:55 回复(0)