4.6 华为笔试题解

T1 字符串排序

我们需要统计文本单词词频，然后根据词频、在文章中出现的位置来排序，然后输出频率最高的 K 个单词。

这道题可以用 topK 算法做到期望复杂度 ，但是在笔试中我们直接排序就可以 AC。

#include <bits/stdc++.h>

using namespace std;

#define umap unordered_map

int n, k;
int no;
vector<string> words;
umap<string, int> id; // map word to id

void process(string& line, umap<int, int>& cnt, umap<int, int>& rank) {
    int r = 0;
    int i = 0;
    while (i < line.size()) {
        while (i < line.size() && line[i] == ' ') ++i;
        int st = i;
        while (i < line.size() && line[i] != ' ') ++i;
        string w = line.substr(st, i - st);
        if (!id.count(w)) {
            id[w] = no++;
            words.push_back(w);
        }
        cnt[id[w]]++;
        if (!rank.count(id[w])) {
            rank[id[w]] = r;
        }
        ++r;
    }
}

int main() {
    cin >> n >> k;
    string line;
    getline(cin, line); // 去掉尾部的 \n

    umap<int, int> title_cnt, text_cnt, rank_1, rank_2;
    no = 0;

    for (int i = 0; i < n; ++i) {
        getline(cin, line);
        process(line, title_cnt, rank_1);
        getline(cin, line);
        process(line, text_cnt, rank_2);
    }

    auto cmp = [&](string& s1, string& s2) {
        int i = id[s1], j = id[s2];
        int f1 = 3 * title_cnt[i] + text_cnt[i], f2 = 3 * title_cnt[j] + text_cnt[j];
        if (f1 != f2) return f1 > f2;
        else if (title_cnt[i] != title_cnt[j]) return title_cnt[i] > title_cnt[j];
        else if (text_cnt[i] != text_cnt[j]) return text_cnt[i] > text_cnt[j];
        else if (rank_1[i] != rank_1[j]) return rank_1[i] < rank_1[j];
        else return rank_2[i] < rank_2[j];
    };
    sort(words.begin(), words.end(), cmp);

    for (int i = 0; i < k; ++i) {
        cout << words[i];
        if (i != k-1) cout << " ";
        else cout << endl;
    }
    return 0;
}

T2 拓扑排序

我们需要找到启动服务的前置服务，并且这些前置服务存在传递关系。这是一道很经典的拓扑排序模板题。

#include <bits/stdc++.h>

using namespace std;

#define maxn 5050

int m, n;
vector<int> g[maxn];
vector<int> ans;
int vis[maxn];
bool open(int x) {
    if (vis[x] == 1) return true;
    else if (vis[x] == -1) return false;
    vis[x] = -1;
    for (auto to : g[x]) {
        if (!open(to)) return false;
    }

    if (x != m) ans.push_back(x);
    vis[x] = 1;
    return true;
}

int readint() {
    int sn = 1;
    char ch = getchar();
    while (!(isdigit(ch) || ch == '-')) ch = getchar();
    int ret = 0;
    if (ch == '-') sn = -1;
    else ret = ch - '0';
    while (isdigit(ch = getchar())) {
        ret = ret * 10 + ch - '0';
    }
    return sn * ret;
}

int main() {
    n = readint(), m = readint();
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i) {
        int num = readint();
        int rely;
        for (int j = 0; j < num; ++j) {
            rely = readint();
            g[i].push_back(rely);
        }
    }

    if (!open(m)) {
        cout << "-1" << endl;
    } else if (ans.empty()) {
        cout << "null" << endl;
    } else {
        for (auto e : ans) {
            cout << e;
            if (e != ans.back()) cout << ",";
            else cout << endl;
        }
    }

    return 0;
}

T3 单调栈

这道题如果没有学过单调栈，有一定难度。可以参考 lc.42 接雨水。下面直接给出代码。

#include <bits/stdc++.h>

using namespace std;

#define maxn 5050

int m, n;
vector<int> height;

int readint() {
    int sn = 1;
    char ch = getchar();
    while (!(isdigit(ch) || ch == '-')) ch = getchar();
    int ret = 0;
    if (ch == '-') sn = -1;
    else ret = ch - '0';
    while (isdigit(ch = getchar())) {
        ret = ret * 10 + ch - '0';
    }
    return sn * ret;
}

int main() {
    n = readint(), m = readint();
    height.resize(m);

    for (int i = 0; i < m; ++i) {
        height[i] = readint();
    }
    height.push_back(0);
    stack<int> st;
    st.push(-1);
    long long ans = 0;
    for (int i = 0; i < m+1; ++i) {
        while (st.top() != -1 && height[st.top()] < height[i]) {
            int h = height[st.top()]; st.pop();
            int pre = st.top();
            h -= min(pre == -1 ? 0 : height[pre], height[i]);
            if (i - pre - 1 >= n && h < 0) {
                int t = (i - pre - 1) / n;
                ans += 1ll * t * (-h);
            }
        }
        st.push(i);
    }
    cout << ans << endl;
    return 0;
}