[Algorithm][综合训练][哈夫曼编码][abb][旋转字符串]详细讲解

---

1.哈夫曼编码

1.题目链接

• 哈夫曼编码

---

2.算法原理详解 && 代码实现

• 哈夫曼编码：核心 -> 让出现次数越多的字符编出来的码越短

  • 是什么：最优的压缩方式
  • 怎么用：
    • 统计每个字符的频次
    • 根据频次构建最优二叉树
    • 根据最优二叉树编码
      

• 解法：利用小根堆，一边构建树，一边计算长度

  #include <iostream>
  #include <vector>
  #include <queue>
  using namespace std;typedef long long LL;int main()
  {int n = 0;cin >> n;priority_queue<LL, vector<LL>, greater<>> heap;while(n--){LL x = 0;cin >> x;heap.push(x);}// 构建最优二叉树/哈夫曼树LL ret = 0;while(heap.size() > 1){LL x1 = heap.top();heap.pop();LL x2 = heap.top();heap.pop();heap.push(x1 + x2);ret += x1 + x2;}cout << ret << endl;return 0;
  }
  

---

2.abb

1.题目链接

• abb

---

2.算法原理详解 && 代码实现

• 解法：动态规划 + 哈希表 -> 子序列问题 -> 以某个位置为结尾来分析问题

  • 状态表示：dp[i]：以i位置元素为结尾的所有的子序列中，有多少个_xx

  • 状态转移方程：
    

  • 返回值：整张dp表的和

  #include <iostream>
  #include <string>
  using namespace std;int main()
  {int n = 0;string str;cin >> n >> str;long long f[26] = { 0 };long long g[26] = { 0 };long long ret = 0;for(int i = 0; i < n; i++){// DPint x = str[i] - 'a';ret += f[x];// Updatef[x] = f[x] + i - g[x];g[x] = g[x] + 1;}cout << ret << endl;return 0;
  }
  

---

3.旋转字符串

1.题目链接

• 旋转字符串

---

2.算法原理详解 && 代码实现

• 解法一：暴力模拟 --> 每次旋转⼀下A字符串，看看是否和B字符串相同
• 解法二：规律 + string接口
  • 如果A能够旋转之后得到B的话，在A倍增之后的新串中，⼀定是可以找到B的
  • 因此，仅需让A倍增，然后查找B即可

  bool solve(string A, string B)
  {if(A.size() != B.size()){return false;}return (A + A).find(B) != string::npos;
  }