本文主要是介绍C++笔试强训day39，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1.神奇的字母（二）
2.字符编码
3.最少的完全平方数
1.神奇的字母（二）
链接
https://ac.nowcoder.com/acm/problem/205832
看输出描述即可知输出次数最多的那个字母即可。
哈希表直接秒了：
#include <iostream>
#include <string>
using namespace std;
int cnt[26];
int m_cnt, keyi;
int main() {string s;while (getline(cin, s)){for (auto c : s)if (c != ' ')cnt[c - 'a']++;for (int i = 0; i < 26; ++i){if (cnt[i] > m_cnt){m_cnt = cnt[i];keyi = i;}}}char ret = 'a' + keyi;cout << ret << endl;return 0;
}2.字符编码
链接https://www.nowcoder.com/practice/c471efdbd33a4a979539a91170c9f1cb?tpId=128&tqId=33774&ru=/exam/oj
即为哈夫曼编码：与该篇中的模版题极为相似-》模版https://blog.csdn.net/cy18779588218/article/details/139304233?spm=1001.2014.3001.5501
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;signed main() {string s;while (cin >> s) {int ret = 0;int cnt[250] = { 0 };for (auto c : s)cnt[c]++;priority_queue<int, vector<int>, greater<int>> pq;for (int n : cnt)if (n != 0)pq.push(n);while (pq.size() != 1) {int top1 = pq.top();pq.pop();int top2 = pq.top();pq.pop();ret += (top1 + top2);pq.push(top1 + top2);}cout << ret << endl;}return 0;
}3.最少的完全平方数
链接https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj
类似完全背包题目：
搞清楚他的状态表示{
dp[i][j] : 从前i个数中挑选，总和恰好为j时，需要挑选的最少个数
}就很好做题了。（不过要先了解过完全背包）
注意留意他的初始化，因为是去最小值，所以可以直接将dp表初始化为INT_MAX，然后初始化一下填表需要用到的位置：
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;int arr[110];
int dp[110][10010];
int n;int main()
{cin >> n;for(int i = 1; i <= 100; ++i)arr[i] = i * i;int r = sqrt(n);memset(dp, 0x3f, sizeof dp);for(int i = 1; i <= r; ++i)dp[i][0] = 0;for(int i = 1; i <= r; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = dp[i - 1][j];if(j >= arr[i])dp[i][j] = min(dp[i - 1][j], dp[i][j - arr[i]] + 1);}}cout << dp[r][n] << endl;return 0;
}当然，也可以进行空间优化。
这篇关于C++笔试强训day39的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
