美团算法岗笔试题 2022.08.06
1. 两种糖，每个盒子装三个，要求每种至少一个，求最多装几盒。
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--) {
int x, y;
cin >> x >> y;
if(x > y)
swap(x, y);
int a = x, b = y - x;
if(a <= b) {
cout << a << endl;
continue;
}
int k = (2 * a + b) / 3;
cout << k << endl;
}
return 0;
} 2. 有一个数组由0，1，-1组成，找一个分割点，分割点左面>=0个数加上右面<=0个数最小 #include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{
int n, res = INT_MAX;
cin >> n;
vector<int> a(n);
vector<int> left(n+1, 0), right(n+1, 0);
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
int tmp = 0;
for(int i = 0; i < n; i ++) {
if(a[i] >= 0) {
tmp ++;
}
left[i+1] = tmp;
}
tmp = 0;
for(int i = n-1; i >= 0; i --) {
if(a[i] <= 0) {
tmp ++;
}
right[i] = tmp;
}
for(int i = 0; i <= n; i ++) {
res = min(res, left[i]+right[i]);
}
cout << res << endl;
return 0;
} 3. 小美有n块魔法石，每块魔法石都有正反两面，每一面上都刻有一个魔法阵，初始状态下，n块魔法石都是正面向上。这n块魔法石的能量刚好可以构建一个大型魔法阵，但是需要至少一半的魔法石向上的一面铭刻的阵法相同才能触发大型魔法阵的效果。小美希望翻转最少数量的魔法石，使得这个大型魔法阵被触发，请问她最少需要翻转多少块魔法石。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> up(n, 0), down(n, 0);
unordered_map<int, vector<int>> m;
unordered_map<int, int> cnt;
int half = (n + 1) / 2;
for(int i = 0; i < n; i ++) {
cin >> up[i];
m[up[i]].push_back(i);
if(m[up[i]].size() >= half) {
cout << 0 << endl;
return 0;
}
}
int res = INT_MAX;
for(int i = 0; i < n; i ++) {
cin >> down[i];
if(down[i] == up[i])
continue;
m[down[i]].push_back(i);
cnt[down[i]] ++;
if(m[down[i]].size() >= half)
res = min(res, cnt[down[i]]);
}
if(res == INT_MAX)
res = -1;
cout << res << endl;
return 0;
}
4. 有n个样本，一共k个类别，按照样本序号给个数组，值是类别，要求划分训练测试集，训练集是类别样本个数/2，向上取整，要求输出训练验证集的序号，从小到大排列。 #include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> train, test;
unordered_map<int, vector<int>> cls;
for(int i = 0; i < n; i ++) {
int tmp;
cin >> tmp;
cls[tmp].push_back(i+1);
}
for(auto it = cls.begin(); it != cls.end(); it ++) {
int len = it->second.size();
int i;
for(i = 0; i < ceil(len/2.0); i ++) {
train.push_back(it->second.at(i));
}
for(; i < len; i ++) {
test.push_back(it->second.at(i));
}
}
sort(train.begin(), train.end());
sort(test.begin(), test.end());
for(int i = 0; i < train.size(); i ++) {
cout << train[i] << " ";
}
cout << endl;
for(int i = 0; i < test.size(); i ++) {
cout << test[i] << " ";
}
cout << endl;
return 0;
} 5. 选择题
（1）优化算法有哪些；
（2）SVM核函数概念；
（3）非参数估计；
类似资料：