8.28 菜鸡的小红书后端笔试 后两道编程

(选择虽然准备的不足，但真的是没想到还会有python, java的程序题。。）

编程用的C++, 都是想到啥就写啥，连写了三题的vector排序。。没啥技术含量

第二题：排了下序直接双循环遍历，不知道是不是超时了，怎么改都是27%，怀疑是不是理解错题目了

看了一些其他人的答案，感觉大概率是mul溢出了

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
static bool cmp(const int& a, const int& b) {
    return a > b;
}
int main() {
    int n, K;
    cin >> n >> K;
    vector<int>a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end(), cmp);
    unordered_map<int, int>res;
    int count = 0;
    int i = 0;
    int j = 0;
    for (i = 0; i < n; i++){
        if (i != n - 1 && a[i] * a[i + 1] < K)break;
        for (j = i + 1; j < n; j++) {
            if (a[i] != a[j]) {
                int mul = a[i] * a[j];
                if (mul >= K) {
                    if (res[a[i]] != a[j]) {
                        res[a[i]] = a[j];
                        count++;
                    }
                }
                else break;
            }
        }
    }
    cout << 2 * count << endl;
    return 0;
}

第三题：按邻接表+bfs思路做的，不确定思路对不对，想的是从边数最少的（至少边数为1）的结点开始匹配，写的很复杂。。不知道为什么没加que.push(graph[k][j])就是27%（感觉应该不需要这句？），但加上就是全部通过。

再看了下，感觉上面说的问题可能是因为我只存了单向的边（本来应该是存双向的），然后发现自己写的编号有点问题，题目里记得是1~n，edges按1~n存了，但这里的graph,indegree,visited都还是编号从0开始的，不过可能正好只存了单向边，所以graph没超出索引。。算是误打误撞吧

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>>edges(n - 1, vector<int>(2, 0));
    for (int i = 0; i < n - 1; i++) {
        cin >> edges[i][0];
        edges[i][1] = i + 2;
    }
    vector<vector<int>>graph(n);
    for (int i = 0; i < n - 1; i++) {
        graph[edges[i][0]].push_back(edges[i][1]);
    }
    int count = 0;
    queue<int>que;
    vector<int>visited(n, 0);
    vector<pair<int, int>>indegree;
    for (int i = 0; i < n; i++) {
        pair<int, int>tmp;
        tmp.first = i;
        tmp.second = graph[i].size();
        indegree.push_back(tmp);
    }
    sort(indegree.begin(), indegree.end(), cmp);
    //从边数为1的点开始配对
    for (int i = 0; i < n; i++) {
        int v = indegree[i].first;
        if (visited[v] == 1)continue;
        que.push(v);
        while (!que.empty()) {
            int k = que.front();
            que.pop();
            for (int j = 0; j < graph[k].size(); j++) {
                if (!visited[graph[k][j]] && !visited[k]) {
                    count++;
                    visited[graph[k][j]] = 1; visited[k] = 1;
                    que.push(graph[k][j]);
                    break;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}