笔试——Day39

第一题

题目

神奇的字母（二）

思路

哈希表统计字符串中每个字母出现的次数

代码

#include<iostream>
#include<string>using namespace std;int main()
{string s;int hash[26] = {0};char res;int maxCount = -1;while(cin >> s){for(auto &e : s){hash[e - 'a']++;if(hash[e - 'a'] > maxCount){res = e;maxCount = hash[e - 'a'];}}}cout << res << endl;return 0;
}

第二题

题目

字符编码

思路

哈夫曼编码，求最短编码长度，利用小堆进行处理

代码

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() 
{string s;while (cin >> s) { int hash[300] = {0};for(auto &e : s){hash[e]++;}priority_queue<int, vector<int>, greater<int>> pq;for(auto &e : hash){if(e) pq.push(e);}int res = 0;while(pq.size() > 1){int a = pq.top(); pq.pop();int b = pq.top(); pq.pop();res += (a + b);pq.push(a + b);}cout << res << endl;}return 0;
}
// 64 位输出请用 printf("%lld")

第三题

题目

最少的完全平方数

思路

动态规划

代码

#include <cstring>
#include <iostream>
using namespace std;const int N = 1e4 + 10;
int dp[N];
int n;int main()
{   // dp[i][j]表示：从前i个数中挑选（1 2 4 9 16...），恰好为j时，最少挑选出几个数// 状态转移方程：// 不选第i个数，dp[i][j] = dp[i - 1][j]// 选第i个数1个，dp[i][j] = dp[i - 1][j - i * i] + 1// 选第i个数2个，dp[i][j] = dp[i - 1][j - 2 * i * i] + 2// ...// 所有选的可能，dp[i][j] = dp[i][j - i * i] + 1cin >> n;memset(dp, 0x3f, sizeof dp);dp[0] = 0;for(int i = 1; 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;
}