#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