首页 > 试题广场 >

字符编码

[编程题]字符编码
  • 热度指数:5116 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
请设计一个算法,给一个字符串进行二进制编码,使得编码后字符串的长度最短。

数据范围:字符串长度满足 ,本题有多组输入

输入描述:
每组数据一行,为待编码的字符串。保证字符串长度小于等于1000。


输出描述:
一行输出最短的编码后长度。
示例1

输入

MT-TECH-TEAM

输出

33
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
int main(){
	char s[3300];
	while(scanf("%s",s) != EOF){
		int n = strlen(s);
		sort(s,s + n);
		priority_queue<int> heap;
		int cnt = 0;
		for(int i = 0,j;i < n;){
			j = i;
			while(j < n && s[j] == s[i]) ++ j;
			heap.push(i - j);
			i = j;
			++ cnt;
		}
		int ret = 0;
		for(int i = 0;i < cnt - 1;++ i){
			int A = heap.top(); heap.pop();
			int B = heap.top(); heap.pop();
			ret -= A + B;
			heap.push(A + B);
		}	
		printf("%d\n",ret);
	}
	return 0;
}
发表于 2015-10-22 10:00:48 回复(14)

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
#define MAX 1000

using namespace std;

int main()
{
    char newString[MAX] = {0};
   while(cin>>newString)
    {
        int i, j;
        int countNum = 0;     //统计不同字符个数
        int sum = 0;              //记录编码后的长度
        int first = 0, second = 0;      //分别记录队列的最小两个值
        int len = strlen(newString);
        priority_queue <int, vector<int>, greater<int> > huffmanQueue;   //定义小值优先级高的队列
         sort(&newString[0], &newString[len]);
    
         for(i = 0; i < len; )
         {
                 j = i;
                 while((j < len)&&(newString[j] == newString[i]))  
                {
                      j++;
                }
               huffmanQueue.push(j - i);   //将字符newString[i]的个数压入队列
                i = j;
               countNum++;
        }
        for(i = 0; i < countNum - 1; i++)  //霍夫曼编码步骤
        {
              first = huffmanQueue.top();
              huffmanQueue.pop();
              second = huffmanQueue.top();
              huffmanQueue.pop();
              huffmanQueue.push(first + second);  
              sum += first + second;
        }
        cout<<sum<<endl;
    }//while
    return 0;
}

发表于 2016-04-03 11:48:58 回复(1)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    string str;
    while( cin >> str ){
        int number = 0,len = 0,i,j,a[1000],l = str.length();
        for(i=0;i<l;i++){//统计各个字符出现次数
            if(str[i] != -1){
                int count = 1;
                for(j=i+1;j<l;j++){
                    if(str[j] == str[i]){
                        str[j] = -1;
                        count++;
                    }
                }
                a[number] = count;
                number++;
            }
        }
        sort(a,a+number);//从小到大排序
        while(number-1){//用一组有序数模拟建立哈夫曼树的过程,不断取前两个合并,再插入有序数组。重复直至数组只有一个数为止。
            int b;
            b = a[0] + a[1];
            len += b; //每次合并一次,代表在其上建枝,即需要一位二进制编码。
            for(i=0;i<number-2;i++)
                a[i] = a[i+2];
            a[number -2] = b;
            number --;
            sort(a,a+number);
        }
        cout << len <<endl;
    }
    return 0;
}
//常规做法,利用优先级队列模拟哈夫曼编码
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
    char str[1002];
    while( cin >> str ){
        int len=0,l = strlen(str),i,j;
        priority_queue< int,vector<int>,greater<int> > hufm;//定义优先队列,值小的在前。
        sort(str,str+l);//排序后会把相同的字符放在一起便于后统计各个字符串个数。
        for(i=0;i<l;){
            j = i;
            while(str[j] == str[i] && j<l )
                j++;
            hufm.push(j - i);
            i = j;
        }
        while( hufm.size() !=  1 ){
            int temp = 0;
            temp = hufm.top(); hufm.pop();
            temp += hufm.top(); hufm.pop();
            len += temp;
            hufm.push(temp);
        }
        cout << len << endl;
    }
}

编辑于 2017-06-29 21:07:50 回复(0)
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)

2楼大佬的思路真是干净高效

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e3 + 3;
char s[maxn];
int main(){
    while(scanf("%s", s) != EOF){
        priority_queue<int, vector<int>, greater<int> > q;//优先级队列 小数优先级高
        int len = strlen(s);
        sort(s, s + len);
        int l = 0, r = 1, cnt = 0;
        while(l < len){//计算各个字母重复的个数 放入优先级队列 小数优先级高
            while(r < len && s[r] == s[l]) {r++;}
            q.push(r - l);
            l = r;
            cnt++;
        }
        int ans = 0;
        for(int i = 0; i < cnt - 1; i++){
            //建树过程 实际上 带权路径长度和 = 所有建树过程中求的和全部加起来
            int a = q.top(); q.pop();
            int b = q.top(); q.pop();
            ans += (a + b);//树的深度约多 被重复计算的次数也越多
            q.push(a + b);
        }
        printf("%d\n", ans);
    }
}
发表于 2018-10-17 23:19:47 回复(0)
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String[] ss = in.nextLine().split("");
			Map<String,Integer> map = new HashMap<String, Integer>();
            //这里有点坑 java7 中split("") 会多出一个空字符串
			for(int i = 1;i<ss.length;i++){
				int value = map.containsKey(ss[i])?map.get(ss[i])+1:1;
				map.put(ss[i], value);//先计算出每个字符出现的次数
			}
			Set<Map.Entry<String,Integer>> set = map.entrySet();
			
            //创建优先队列
			PriorityQueue<Nodes> nodeQueue = new PriorityQueue<Nodes>();
			for (Map.Entry<String,Integer> object : set) {
				Nodes node = new Nodes();
				node.priority = object.getValue();
				node.context = object.getKey();
				nodeQueue.add(node);
			}
			Nodes root = null;
			while(nodeQueue.size()!=1){
				Nodes node1 = nodeQueue.peek();
				nodeQueue.remove(node1);
				
				Nodes node2 = nodeQueue.peek();
				nodeQueue.remove(node2);
				
				root = new Nodes();
				root.left = node1;
				root.right = node2;
				root.priority = node1.priority+node2.priority;
				
				nodeQueue.add(root);
				
			}
			getMap(root, 0,map);//把各个字符的二进制长度记录到map中
			int count = 0;
			for(int i = 1;i<ss.length;i++){
				count += map.get(ss[i]);
			}
			System.out.println(count);
			
		}
	}
	
	public static void getMap(Nodes root,int deep,Map<String,Integer> map){
		if(root.left==null&&root.right==null){
			map.put(root.context, deep);//字符的二进制长度等于哈夫曼树的深度
			return;
		}
		getMap(root.left, deep+1,map);
		getMap(root.right, deep+1 ,map);
	}
	
}
class Nodes implements Comparable<Nodes>{
	int value;
	String context;
	int priority;
	Nodes left;
	Nodes right;
	
	@Override
	public int compareTo(Nodes o2) {
		int numbera = this.priority;
        int numberb = o2.priority; 
        if(numberb < numbera){  
            return 1;  
        }  
        else if(numberb>numbera){  
            return -1;  
        }  
        else{  
            return 0;  
        }  
	}
}

发表于 2016-04-13 16:42:05 回复(0)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int main()
{     char s[4010];     while(cin>>s)     {         int n = strlen(s);         sort(s, s+n);         priority_queue<int> heap;         int count = 0;         for(int i=0,j;i<n;)         {             j = i;             while(j<n && s[j]==s[i])                 j++;             heap.push(i-j);             i = j;             count++;         }         int result = 0;         for(int i=0;i<count-1;i++)         {             int a = heap.top();             heap.pop();             int b = heap.top();             heap.pop();             int c = a + b;             result -= c;             heap.push(c);         }         cout<<result<<endl;     }     return 0;
}

发表于 2017-10-17 09:51:09 回复(0)

//

//  main.cpp

//  lainxi

//

//  Created by Lando on 17/7/30.

//  Copyright © 2017 Lando. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <vector>

#include <deque>

#include <set>

#include <stack>

#include <map>

#include<math.h>

#include<algorithm>

#include<string>

#include <queue>

using namespace std;

int main(){

    string s;

    while(getline(cin,s)){

        int len=s.length();

         priority_queue<int,vector<int>,greater<int>> num;

        map<char,int>m;

        for(int i=0;i<len;i++){

            m[s[i]]++;

        }

        int cnt=0;

        map<char,int>::iterator it;

        for(it=m.begin();it!=m.end();it++)

        {num.push(it->second);

            cnt++;

        }

        

        

    int res=0;

    while(--cnt){

        int a=num.top();num.pop();

        int b=num.top();num.pop();

        num.push(a+b);

        res+=a+b;

    

    }

    cout<<res<<endl;

    }

    return 0;

}

发表于 2017-07-31 17:04:41 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main () {
    char s[1000];
    while (scanf("%s", s) != EOF) {
        int n = strlen(s);
        int a[256] = {0};
        int b[256] = {0};
        for (int i = 0; i < n; i++) {
            a[(int)s[i]]++;
        }

        int count = 0;
        for (int i = 0; i < 256; i++) {
            if (a[i] > 0) {
                b[count++] = a[i];
            }
        }

        priority_queue<int, vector<int>, greater<int>> mypq;

        for (int i = 0; i < count; ++i) {
            mypq.push(b[i]);
        }

        int ret = 0;
        for (int i = 1; i < count; i++) {
            int A = mypq.top(); mypq.pop();
            int B = mypq.top(); mypq.pop();
            ret += A + B;
            mypq.push(A+B);
        }
        cout << ret << endl;
    }
    return 0;
}

发表于 2017-03-21 20:59:01 回复(0)
就是个哈夫曼编码。
1)将待编码的字符按照出现频率降序排列;
2)将出现次数最少的两个字符a,b的编码分别增加前缀0,1;
3)然后将这两个字符a,b合并,为新的字符a',并将出现次数相加作为新的字符的出现次数;
4)删除最后一个字符。继续执行1,直到待编码的字符个数为1个时,停止。
#include<bits/stdc++.h>
using namespace std;
typedef pair<unordered_set<char>,int> type;
bool comp(const type &a,const type &b){
	return a.second > b.second;
}
int main(){
	for(string str;getline(cin,str);){
		vector<int> hash(256,0); // each char count
		vector<type> huffcoding; // tobe huffed
		for(int i=0;i<str.length();++hash[str[i++]]);
		for(int i=0;i<256;++i){
			if (!hash[i]) continue;
			unordered_set<char> s;
			s.insert(i);
			huffcoding.push_back(make_pair(s,hash[i]));
		}
		vector<int> huffcode(256,0); // each char's huffcode len
		for(int i=huffcoding.size();i>1;i=huffcoding.size()){
			sort(huffcoding.begin(),huffcoding.end(),comp);
			for(auto c:huffcoding[i-2].first) huffcode[c]++;
			for(auto c:huffcoding[i-1].first) huffcode[c]++;
			for(auto c:huffcoding[i-1].first) huffcoding[i-2].first.insert(c);
			huffcoding[i-2].second+=huffcoding[i-1].second;
			huffcoding.pop_back();
		}
		int len;
		for(int i=len=0;i<256;len+=hash[i]*huffcode[i],++i);
		cout<<len<<endl;
	}
	return 0;
}

发表于 2016-08-16 16:49:07 回复(3)
i-i头像 i-i
字符是什么不需要存,哈夫曼树进行深度优先搜索时直接计算所有的叶节点(叶节点指的是左右孩子均为null的情况,如果只有一种字符,也就是只有一个根,那么属于特殊情况要另算)
import java.util.*;

public class Main {
    static class Node {
        int count;
        Node leftChild;
        Node rightChild;

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

        public Node(int count, Node leftChild, Node rightChild) {
            this.count = count;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    static int getLength(Node root, int height) {
        if (root.leftChild == null && root.rightChild == null)
            return root.count * height;
        else
            return getLength(root.leftChild, height + 1) + getLength(root.rightChild, height + 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String string = scanner.nextLine();
            HashMap<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < string.length(); i++) {
                if (map.containsKey(string.charAt(i)))
                    map.put(string.charAt(i), map.get(string.charAt(i)) + 1);
                else
                    map.put(string.charAt(i), 1);
            }
            PriorityQueue<Node> heap = new PriorityQueue<>(map.size(), new Comparator<Node>() { @Override public int compare(Node o1, Node o2) {
                    return o1.count - o2.count;
                }
            });
            for (Integer count : map.values()) {
                heap.add(new Node(count));
            }
            if (heap.size() == 1) {
                System.out.println(heap.poll().count);
                continue;
            }
            while (heap.size() > 1) {
                Node leftChild = heap.poll();
                Node rightChild = heap.poll();
                heap.add(new Node(leftChild.count + rightChild.count, leftChild, rightChild));
            }
            System.out.println(getLength(heap.poll(), 0));
        }
    }
}

编辑于 2017-09-05 14:46:47 回复(0)
//思路就是找到最小的两个值,求累加和,结果就是哈夫曼权值
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    string str;
    while(cin >> str)
    {
        char n[256];
        memset(n,0,sizeof(n));
        for(int i=0;i<str.size();i++)
        {
            n[str[i]]++;
        }
        vector<int> num;
        for(int i=0;i<256;i++)
        {
            if(n[i]!=0)
            {
                num.push_back(n[i]);
            }
        }
        int sum = 0;
        while(num.size()>1)
        {
            sort(num.begin(),num.end());
            int temp = num[0]+num[1];
            num.erase(num.begin());
            num.erase(num.begin());
            num.push_back(temp);
            sum +=temp;
        }
        cout << sum << endl;
    }
    return 0;
}

发表于 2016-10-06 16:08:07 回复(0)
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<cmath>
#include<functional>
#include<sstream>
#include<algorithm>
using namespace std;
int GetLen(string str)
    {
    int len=str.length();
    map<char,int> m;
    for(int i=0;i<len;++i)
        {
        m[str[i]]++;
    }
   // priority_queue<int,greater<int>> p;
        priority_queue<int,vector<int>,greater<int>> p;//(m.begin(),m.end());

    auto ite=m.begin();
    while(ite!=m.end())
        {
        p.push(ite->second);
        ++ite;
    }
    int count=m.size();
    int ret=0;
    for(int i=0;i<count-1;++i)
        {
        int v1=p.top();
        p.pop();
        int v2=p.top();
        p.pop();
        ret+=v1+v2;
        p.push(v1+v2);
        
    }
    cout<<ret<<endl;
    return ret;
}
int main(void)
    {
    string str;
    while(cin>>str)
        {
        GetLen(str);
    }
    return 0;
}
发表于 2016-09-10 00:00:45 回复(0)
//瞎弄个哈夫曼树
using namespace std;
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
struct HT
{
	map<int,int> tree;//统计子树种高度为int的数目int
	int times;
	HT(){}
	HT(int t)
	{
		times=t;
	    tree.insert(make_pair(0,t));
	}
};

struct cmp
{
	bool operator()(const HT & a,const HT & b)
    {
	     return a.times>b.times;
    }
};

int main()
{
	string str;
	while(cin>>str)
	{
		map<char,int> ch;
		for(int i=0;i<str.size();i++)
			ch[str[i]]=ch[str[i]]+1;

		priority_queue <HT,vector<HT>,cmp> ms;
		for(auto it=ch.begin();it!=ch.end();it++)
			ms.push(HT(it->second));

		while(ms.size()>1)
		{
			HT first = ms.top();
			ms.pop();
			HT second = ms.top();
			ms.pop();
			
			HT three;
			three.times = first.times+second.times;
			for(auto it = first.tree.begin();it!=first.tree.end();it++)
				three.tree[(it->first+1)]=it->second + three.tree[(it->first+1)];

			for(auto it = second.tree.begin();it!=second.tree.end();it++)
				three.tree[(it->first+1)]=it->second + three.tree[(it->first+1)];

			ms.push(three);
		}

		int sum=0;
		for(auto it = ms.top().tree.begin();it!=ms.top().tree.end();it++)
			sum+= (((it->first==0)?1:it->first)*(it->second));
		cout<<sum<<endl;
	}
	return 0;
}


发表于 2016-08-23 16:39:23 回复(0)

哈夫曼编码: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)
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)
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s = sc.next();
            char c[] = s.toCharArray();
            int n = s.length();
            Arrays.sort(c);
            PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
            int cnt = 0;
            for(int i = 0,j;i < n;){
                j = i;
                while(j < n && c[j] == c[i]) ++ j;
                heap.offer(j - i);
                i = j;
                ++ cnt;
            }
            int ret = 0;
            for(int i = 0;i < cnt - 1;++ i){
                int a = heap.poll(); 
                int b = heap.poll(); 
                ret += a + b;
                heap.offer(a + b);
            }  
            System.out.println(ret);
        }
    }
}


编辑于 2017-03-21 12:56:20 回复(0)
没啥耐心,变量名用的比较混乱。
import sys

a = []
for line in sys.stdin:
    a += line.split()
    
result = []
for item in a:
    temp = []
    hashmap = {}
    # 字典转列表然后升序排序
    for code in list(item):
        if code in hashmap:
            hashmap[code] += 1
        else:
            hashmap[code] = 1
    temp += sorted(hashmap.items(), key=lambda s: s[1])

    # 列表转字典,并清空权重
    b = temp.copy()
    for i in range(len(b)):
        b[i] = (b[i][0],0)
    b = dict(zip([x[0] for x in b], [x[1] for x in b]))

    # temp:value升序的元组列表
    # b:1权重字典
    def search(kv):
    # 输入元组列表,输出最小元组
        min = kv[0][1]
        char = kv[0][0]
        index = 0
        for i in range(len(kv)):
            if kv[i][1]<= min:
                min = kv[i][1]
                char = kv[i][0]
                index = i
        kv.pop(index)
        return min, char
        
    def hfm():
        #哈夫曼树主体,选择value最小的节点,
        while len(temp) != 1:
            t1,c1 = search(temp)
            t2,c2 = search(temp)
            for any in c1:
                b[any] += 1
            for any in c2:
                b[any] += 1
            temp.append((c1+c2,t1+t2))
    
    hfm()

    # 此时b是树权重字典
    count = 0
    for code in list(item):
        count += b[code]
    print(count)


发表于 2023-04-05 21:26:28 回复(0)
from collections import Counter
from heapq import heapify, heappop, heappush


class Node:
    def __init__(self, weight: int, value: str = None, left: 'Node' = None, right: 'Node' = None):
        self.weight = weight
        self.value = value
        self.left = left
        self.right = right

    def __lt__(self, other: 'Node') -> bool:
        return self.weight < other.weight

    def __eq__(self, other: 'Node') -> bool:
        return self.weight == other.weight


def main1(string: str) -> None:
    def dfs(root: Node, depth: int) -> None:
        nonlocal res
        if not root:
            return
        if root.value is not None:
            res += root.weight * depth
        root.left and dfs(root.left, depth + 1)
        root.right and dfs(root.right, depth + 1)

    chars = list(string)
    counter = Counter(chars)

    pq = []
    for value, weight in counter.items():
        pq.append((weight, Node(weight, value)))
    heapify(pq)

    while len(pq) >= 2:
        _, left = heappop(pq)
        _, right = heappop(pq)
        parent = Node(left.weight + right.weight, None, left, right)
        heappush(pq, (parent.weight, parent))

    root = pq[0][1]
    res = 0
    dfs(root, 0)
    print(res)



while True:
    try:
        string = input()
        main1(string)
    except EOFError:
        break

发表于 2022-02-23 00:24:44 回复(0)
这题真的是简单题么?
发表于 2021-10-21 20:46:12 回复(0)