8.8 美团笔试AK代码
题目较为简单，但是第一题也是醉了，交了好多次才完全通过。😂😂😂
第一题：直接排序
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
sort(a.begin(), a.end());
if (k == 0) {
cout << "YES\n";
cout << 1 << '\n';
} else {
int ans = a[k - 1] + 1;
int t = lower_bound(a.begin(), a.end(), ans) - a.begin();
if (ans <= n && t == k) {
cout << "YES\n";
cout << ans << '\n';
} else {
cout << "NO\n";
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
} 第二题：简单的字符串处理
import sys
line = sys.stdin.readline().strip()
pre = "$"
ans = []
for c in line:
if c != pre and c != " ":
ans.append(c)
if c != " ":
pre = c
print("".join(ans)) 第三题：有序集合（注意数据溢出）
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, x;
long long ans = 0;
set<int> S;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
auto it = S.lower_bound(x);
if (it != S.begin()) {
--it;
ans += 1LL * i * (*it);
}
S.emplace(x);
}
cout << ans << '\n';
return 0;
} 第四题：并查集
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
vector<int> fa(N), size(N);
for (int i = 0; i < N; ++i) {
fa[i] = i;
size[i] = 1;
}
function<int(int)> find_set = [&](int x) { return x == fa[x] ? x : (fa[x] = find_set(fa[x])); };
auto union_sets = [&](int x, int y) -> bool {
x = find_set(x), y = find_set(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
swap(x, y);
}
fa[y] = x;
size[x] += size[y];
return true;
};
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
for (int i = 0; i < n / 2; ++i) {
if (a[i] != a[i + n / 2]) {
union_sets(a[i], a[i + n / 2]);
}
}
unordered_map<int, vector<int>> mp;
for (int i = 0; i < N; ++i) {
mp[find_set(i)].emplace_back(i);
}
int ans = 0;
for (auto it = mp.cbegin(); it != mp.cend(); ++it) {
ans += it->second.size() - 1;
}
cout << ans << '\n';
return 0;
} 第五题：二叉树中序遍历，直接模拟交换
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k, l, r, x;
cin >> n >> m >> k;
vector<TreeNode *> nodes(n + 1);
for (int i = 1; i <= n; ++i) {
nodes[i] = new TreeNode(i);
}
nodes[0] = nullptr;
for (int i = 1; i <= n; ++i) {
cin >> l >> r;
nodes[i]->left = nodes[l];
nodes[i]->right = nodes[r];
}
while (m--) {
cin >> x;
swap(nodes[x]->left, nodes[x]->right);
}
vector<int> ans;
function<void(TreeNode *)> Dfs = [&](TreeNode *root) {
if (!root) {
return;
}
Dfs(root->left);
ans.emplace_back(root->val);
Dfs(root->right);
};
Dfs(nodes[k]);
for (int i = 0; i < n; ++i) {
cout << ans[i] << " \n"[i == n - 1];
}
return 0;
} 
CVTE公司福利 377人发布