#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;
}
#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;
}
#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;
}
}
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;
}
}
}
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);
}
}
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;
}
}
}
#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;
}
//
// 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;
}
#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;
}
#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;
}
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));
}
}
} //思路就是找到最小的两个值,求累加和,结果就是哈夫曼权值
#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;
}
//瞎弄个哈夫曼树
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;
}
哈夫曼编码: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);
}
}
}
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; } } }
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);
}
}
}
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) 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