笔试

账单总结

January:2
clothe:-120.00 teach:+1050.50
February:1
teach:+550.55
March:1
important:+100.50
April:3
sugoi:-88.88 oishii:-99.99 subarashi:+999.98
May:1
nomay:-1024.00
June:4
one:+10.00 two:+20.00 three:+30.00 four:+40.00
July:1
important:+100.50
August:1
important:+100.50
September:1
important:+100.50
October:1
important:+100.50
November:1
important:+100.50
December:1
important:+100.50

January:+930.50
February:+550.55
March:+100.50
April:+811.11
May:-1024.00
June:+100.00
July:+100.50
August:+100.50
September:+100.50
October:+100.50
November:+100.50
December:+100.50
May January

#include <iostream>
#include  <string>
#include  <iomanip>
using namespace std;

//字符串->float
float f(string s)
{
    int n = s.size();
    int i;
    float b = 0,a = 0;
    for(i = 0; i < n; i ++)
    {
        if(s[i] == '.') break;
        else a = a* 10 + s[i] -48;
    }
    for(int i = n-1; i >=0; i --)
    {
        if(s[i] == '.') break;
        else b= b/10 +s[i] -48;
    }
    b/=10;
    return a+b;
}

int main() {
    float maxout = 0;
    float maxin = 0;
    string maxout_m, maxin_m;

    for(int i = 0; i < 12; i ++)
    {
        string a;
        cin >> a;
        int k = a.find(':');
        string m = a.substr(0, k);
        int x = stoi(a.substr(k + 1));
        string de;
        float sum = 0, in = 0, out = 0;//in当月输入，out当月输出
        for(int j = 0; j < x; j ++)
        {
            cin >> de;
            int p = de.find(':');
            string r = de.substr(p+1);
            float val = f(r.substr(1));
            if(r[0] == '-') sum -= val, out += val;
            else sum += val, in += val;
        }

        string res = m;
        res += ':';
        if(sum > 0) res += '+';
        cout << res;
        cout << fixed << setprecision(2) << sum << endl;//保留两位小数 头文件<iomanip>

        if(maxin < in) maxin = in, maxin_m = m;
        if(maxout < out) maxout = out, maxout_m = m;
    }
    cout << maxout_m << " " << maxin_m << endl;

    return 0;
}

面试

阿里云-给定字符，找出频率最高的k个字符，频率由高到低输出这k个字符

哈希map存储频数，大小为k的小根堆根据频数排序，最后倒序输出
时间复杂度：O(max(n, Clogk))

1. 得到频数O（n）
2. 设共有C个不同的字符，C最大为128，需将C个字符添加到大小为k的小根堆中，O（Clogk）
3. 从堆中取出元素，O（k)
4. reverse()，O（k)

空间复杂度：O(n)，哈希map

#include <iostream>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;

struct cmp{
    bool operator()(pair<char, int> &a, pair<char, int> &b)
    {
        return a.second > b.second || (a.second == b.second && a.first < b. first);
    }
};

string StrFreqTopK(string s, int k){
    string res;

    unordered_map<char, int> ump;
    for(auto &s : s) ++ump[s];

    priority_queue<pair<char, int>, vector<pair<char, int>>, cmp> pq;

    for(auto &[ch, i] : ump)
    {
        if(pq.size() < k) pq.push({ch, i});
        else
        {
            if(i > pq.top().second || (i == pq.top().second && ch > pq.top().first))
            {
                pq.pop();
                pq.push({ch, i});
            }
        }
    }

    for(int i = 0; i < k; i ++)
    {
        res.push_back(pq.top().first);
        pq.pop();
    }

    reverse(res.begin(),res.end());

    return res;
}


int main() {
    string s;
    int k;
    cin >> s >> k;
    cout << StrFreqTopK(s, k) << endl;

    return 0;
}

达摩-寻找二叉树的一个和最大的递增序列，返回该值