目錄

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;
}

當然，也可以進行空間優化。