昨天上午有课，失策了，今天把哈夫曼树看了，没想到算法笔记里的哈夫曼树只是一笔带过了，并不难，今天就到此为止了哈哈，回去背专业课了，明天看看字符串hash和kmp算法（kmp算法之前在力扣刷过，相当于复习了）
合并果子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;//小顶堆
int n, ans, tmp;
int main()
{
cin >> n;
while (n--)
{
cin >> tmp;
q.push(tmp);
}
while (q.size() > 1)
{
int x = q.top();
q.pop();
int y = q.top();
q.pop();
q.push(x + y);
ans += x + y;
}
cout << ans;
}
哈夫曼树思想的一种实际问题求解，其实没有用到构建树，有点像贪心。使用了小顶堆，非常不错。所谓哈夫曼树就是一棵，n个节点，都为叶子节点，带权路径最短的树。
最小前缀编码长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;//小顶堆
int n, ans, tmp, v[26];
int main()
{
string s;
cin >> s;
for (char c : s)
{
v[c - 'A']++;
}
for (int i : v)
{
if (i > 0) q.push(i);
}
while (q.size() > 1)
{
int x = q.top();
q.pop();
int y = q.top();
q.pop();
q.push(x + y);
ans += x + y;
}
cout << ans;
}
这道题依旧没有建哈夫曼树，直接用的小顶堆，直接把字母出现次数当作权值即可。