笔试——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] + 1
    cin >> 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;
}