本文主要是介绍[Algorithm][综合训练][字符编码][最少的完全平方数][游游的字母串]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 1.字符编码
- 1.题目链接
- 2.算法原理详解 && 代码实现
- 2.最少的完全平方数
- 1.题目链接
- 2.算法原理详解 && 代码实现
- 3.游游的字母串
- 1.题目链接
- 2.算法思路详解 && 代码实现
1.字符编码
1.题目链接
- 字符编码
2.算法原理详解 && 代码实现
- 解法:给一个字符串进行二进制编码,使得编码后的字符串长度最短 --> 哈夫曼编码
#include <iostream> #include <string> #include <vector> #include<queue> using namespace std;int main() {string str;while(cin >> str){// 1.统计每个字符的频次int hash[300] = { 0 };for(const auto& ch : str){hash[ch]++;}// 2.将所有的频次放入堆中priority_queue<int, vector<int>, greater<>> heap;for(int i = 0; i < 300; i++){if(hash[i]){heap.push(hash[i]);}}// 3.哈夫曼编码int ret = 0;while(heap.size() > 1){int x1 = heap.top();heap.pop();int x2 = heap.top();heap.pop();ret += x1 + x2;heap.push(x1 + x2);}cout << ret << endl;}return 0; }
2.最少的完全平方数
1.题目链接
- 最少的完全平方数
2.算法原理详解 && 代码实现
- 思路:从一些数里面选,每个数都可以选无穷多次,在限定条件下,达到目的
- 解法:完全背包 -> 空间优化版本
-
状态表示:
dp[i][j]
:从前i
割数中挑选,总和恰好为j
时,最少挑出来几个数 -
状态转移方程:
-
初始化:
-
返回值:
dp[sqrt(n)][n]
#include <iostream> #include <cstring> using namespace std;const int N = 1e4 + 10;int main() {int n = 0;cin >> n;int dp[N];memset(dp, 0x3f, sizeof dp);dp[0] = 0;for(int i = 1; i * i <= n; i++){for(int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}cout << dp[n] << endl;return 0; }
-
3.游游的字母串
1.题目链接
- 游游的字母串
2.算法思路详解 && 代码实现
-
解法:暴力枚举所有可能变成的字符情况
- 如何求变化次数:
min(abs(a - z), 26 - abs(a - z))
#include <iostream> #include <cmath> #include <string> using namespace std;int main() {string str;cin >> str;int ret = 0x3f3f3f3f;for(char ch = 'a'; ch <= 'z'; ch++) // 枚举变成什么字符{int sum = 0;for(auto x : str){sum += min(abs(x - ch), 26 - abs(x - ch));}ret = min(ret, sum);}cout << ret << endl;return 0; }
- 如何求变化次数:
这篇关于[Algorithm][综合训练][字符编码][最少的完全平方数][游游的字母串]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!