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;
}
投递美团等公司8个岗位 >