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

当然，也可以进行空间优化。