来源：https://mp.weixin.qq.com/s/KvN9evrjDsgzDowh_Ixf7Q
给定原始二叉树和参照二叉树(输入的二叉树均为满二叉树，二叉树节点的值范围为[1,1000]，二叉树的深度不超过1000)，现对原始二叉树和参照二叉树中相同层级目值相同的节点进行消除、消除规则为原始叉树和参照二叉树中存在多个值相同的节点只能消除等数量的、消除后的节点变为无效节点，请按节点值出现频率从高到低输出消除后原始二叉树中有效节点的值(如果原始二叉树消除后没有有效节点返回0)。
输入描述
原始二叉树中的节点个数
原始二叉树
参照二叉树中的节点个数
参照二叉树
输出描述
原始二叉树中有效节点的值，按出现频率从高到低排序(相同频率的值按大小排序)，相同频率的值按降序排列。
输入样例
7
1 3 3 3 4 5 6
3
2 3 4
输出样例
36541
说明
原始二叉树A消除参照二叉树B中的重复元素后，有效节点剩余2个3，1个6，1个5，1个4，1个1，3出现的频率2，6、5、4、1出现的频率为1，按值从大到小排序、所以排序结果为36541。
思路与代码
二叉树的遍历。
- 按照题目要求构建二叉树。
- 统计参照二叉树每一层节点的出现次数，这一步可以使用哈希表来完成。
- 遍历原始二叉树，每一层的节点减去当前参照二叉树的对应的结点的值的数量即可。
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
int main() {
int m;
cin >> m;
vector<int> nums1(m);
for (int i = 0; i < m; i++) {
cin >> nums1[i];
}
int n;
cin >> n;
vector<int> nums2(n);
for (int i = 0; i < n; i++) {
cin >> nums2[i];
}
vector<unordered_map<int, int>> nums2_cnt(1001);
queue<int> q;
q.push(0);
int depth = 0;
while (q.size()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int node = q.front();
q.pop();
nums2_cnt[depth][nums2[node]]++;
if (node * 2 + 1 < n) {
q.push(node * 2 + 1);
q.push(node * 2 + 2);
}
}
depth++;
}
vector<int> nums1_cnt(1001);
for (const auto &num : nums1) {
nums1_cnt[num]++;
}
q = queue<int>();
q.push(0);
depth = 0;
while (q.size()) {
int sz = q.size();
unordered_map<int, int> cur;
for (int i = 0; i < sz; i++) {
int node = q.front();
q.pop();
cur[nums1[node]]++;
if (node * 2 + 1 < m) {
q.push(node * 2 + 1);
q.push(node * 2 + 2);
}
}
for (const auto &item : cur) {
if (nums2_cnt[depth][item.first] > 0) {
nums1_cnt[item.first] = max(nums1_cnt[item.first] - nums2_cnt[depth][item.first], 0);
}
}
depth++;
}
vector<PII> ans;
for (int i = 0; i < 1001; i++) {
if (nums1_cnt[i] > 0) {
ans.push_back({i, nums1_cnt[i]});
}
}
sort(ans.begin(), ans.end(), [](const PII &a, const PII &b) {
return a.second == b.second ? a.first > b.first : a.second > b.second;
});
for (const auto &item : ans) {
cout << item.first;
}
}你正在为一个社交网络平台开发好友推荐功能。
平台上有N个用户(每个用户使用1到N的整数编号)，同时系统中维护了用户之间的好友关系。
为了推荐新朋友，平台决定采用“共同好友数量"作为衡量两个用户之间相似度的标准。
系统根据输入用户编号K，输出与此用户K相似度最高的前L个用户ID来推荐给用户K。
相似度定义:两个用户非好友，两个用户的相似度为拥有的共同好友数(例如用户A和用户B，只有共同好友C和D，相似度=2)
输入描述
第一行包含四个整数 N，M 、K和L，分别表示用户的数量(N)，好友记录条数(M)、查询的用户编号(K)和推荐的好友数量(L)。接下来 M 行，每行包含两个整数编号X和Y，表示编号为X和Y用户是好友。
1.输入格式都是标准的，无需考虑输出异常场景(不会包含用户和自己是好友的输入，例如11)
2.用户数不超过1024，用户编码最大1024
3.好友记录数不超过10240
输出描述
根据输入K和L，输出和用户K相似度最高的L个用户编码。
1.输出相似度最高的前L个用户编码，按照相似度从高到低排序
2.如果有相似度相同的可能好友，按照用户编号从小到大排序
3.如果推荐的好友个效不足L个，则推荐与用户K无无共同好友关系的用户(陌生人)作为可能好友，如果推荐仍不满足L个用户，剩余推荐用户编码使用0来占位
输入样例
6 7 3 2
1 2
1 3
2 3
3 4
3 5
4 5
5 6
输出样例
6 0
说明
输入包含了6个用户，7条好友记录，给用户ID编号为3的用户推荐2个好友。
输出只有编号为6的用户可能是编号3用户的可能好友;
尝试推荐与编号3用户无共同好友的其他用户，由于除编号为6的用户之外，其他用户和编号3用户都是好友，所以找不到陌生人作为推荐的第二个用户;
推荐结果不足2个用户，所以推荐的第二个用户编码使用0来占位补足。
思路与代码
哈希表+遍历。
咋一看是图论的题目，实际上就是一个哈希表。
- 首先将所有的人的好关系建立一个哈希表。
- 遍历除了K以外的所有人，判断是否与K是直接的好友关系，是的话则直接跳过；否则统计两个哈希表的交集，作为二者共同好友的数量。
- 最后统计即可，记得不够的补0。
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
int main() {
int N, M, K, L;
cin >> N >> M >> K >> L;
vector<unordered_set<int>> friends(N + 1);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
friends[a].insert(b);
friends[b].insert(a);
}
vector<PII> ans;
for (int i = 1; i <= N; i++) {
if (friends[K].find(i) == friends[K].end() && i != K) {
unordered_set<int> intersection;
for (int j : friends[K]) {
if (friends[i].find(j) != friends[i].end()) {
intersection.insert(j);
}
}
ans.push_back({intersection.size(), i});
}
}
sort(ans.begin(), ans.end(), [](const PII& a, const PII& b) {
return a.first == b.first ? a.second < b.second : a.first > b.first;
});
vector<int> cout_ans;
for (int i = 0; i < L && i < ans.size(); i++) {
cout_ans.push_back(ans[i].second);
}
for (int i = ans.size(); i < L; i++) {
cout_ans.push_back(0);
}
for (int i = 0; i < cout_ans.size(); i++) {
cout << cout_ans[i];
if (i != cout_ans.size() - 1) {
cout << " ";
}
}
}维修工要给n个客户更换设备，为每个用户更换一个设备。维修工背包内最多装k个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级level用数字表示，数字小的优先级高。维修工从公司出发，给n个客户更换设备，最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线，请参考样例1图示。
输入描述
第一行两个正整数 n,k(1≤k≤n≤2000),表示客户数和维修工背包容量。
第二行两个正整数 x,y ，用空格分隔(1 ≤ ,y ≤ 10^6),表示公司的坐标
接下来n行每行三个正整数 xi,yi,leveli;，用空格分隔(1≤xi,yi≤10^6,1≤leveli<=n).(xi,yi)表示第i个客户的位置坐标，leveli表示第i个客户的优先级，保证所有客户优先级不同，客户和公司坐标不会重叠。
输出描述
输出最短总距离，结果四舍五入并保留一位小数，例如:9.0。
输入样例
3 2
1 1
3 1 1
1 2 2
3 2 3
输出样例
9.2
思路与代码
动态规划。
首先将客户按照优先级排序，从头到尾遍历。
f[i,j]表示从第i个客户开始，剩余的维修工具为j，遍历完所有的客户的最短路是多少。
对于每个客户来讲，有两种选择：
- 直接回到公司补充维修工具，走到下一个城市。f[i+1,k-1]
- 如果当前维修工具足够，那么直接走到下一个城市。f[i+1,j-1]
注意计算距离即可。
PS 要记得最后再四舍五入，否则可能会导致结果不对。
#include <bits/stdc++.h>
using namespace std;
class Client {
public:
int x, y, level;
};
double distance(const Client &a, const Client &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
vector<vector<double>> f;
vector<Client> clients;
int n, k, x, y;
double dfs(int i, int j) {
// 从当前点回到公司的距离
if (f[i][j] > 1e-6) {
return f[i][j];
}
double dis = distance(clients[i], clients[0]);
if (i == clients.size() - 1) {
// 到达最后一个客户，直接返回
return dis;
}
// 回到公司，再去下一个客户的距离
double ans = dis + distance(clients[i + 1], clients[0]) + dfs(i + 1, k - 1);
if (j > 0) {
// 直接去下一个客户的距离
ans = min(ans, dfs(i + 1, j - 1) + distance(clients[i + 1], clients[i]));
}
f[i][j] = ans;
return ans;
}
int main() {
cin >> n >> k;
f.resize(n + 1, vector<double>(k, 0));
cin >> x >> y;
clients.push_back({x, y, 0});
for (int i = 0; i < n; i++) {
int x, y, level;
cin >> x >> y >> level;
clients.push_back({x, y, level});
}
sort(clients.begin(), clients.end(), [](const Client &a, const Client &b) {
return a.level < b.level;
});
double ans = distance(clients[1], clients[0]) + dfs(1, k - 1);
printf("%.1lf\n", ans);
}