拼多多 9.1 大数据研发笔试题
三题得分 100, 100, 30
第一题
给定m个数字及一个数字n, 将这m个数字进行如下方式排序后取出前n项并输出
1. 偶数排在奇数前面
2. 相同奇偶性时，数值越大排在越靠前的位置
思路：
荷兰国旗问题 + 排序
1. 偶数排在奇数前面
2. 相同奇偶性时，数值越大排在越靠前的位置
思路：
荷兰国旗问题 + 排序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e8 + 10;
int arr[maxn];
int n;
void print_ans(int lo, int hi) {
for (int i = lo; i < hi - 1; ++i) cout << arr[i] << ",";
cout << arr[hi - 1];
}
int main() {
int num;
char ch;
int size = 0;
while (cin >> num >> ch) {
arr[size++] = num;
if (ch == ';') break;
}
cin >> n;
int cur = 0, lo = 0;
while (cur < size) {
if (arr[cur] % 2 == 0) swap(arr[cur], arr[lo++]);
++cur;
}
sort(arr, arr + lo, greater<int>());
sort(arr + lo, arr + size, greater<int>());
print_ans(0, n); cout << endl;
return 0;
}
第二题
小梅和他男朋友小白玩游戏，
小梅有N <= 8张牌， 小白有 M <= N张牌, 小梅将牌从左往右铺开（不一定排序） ，小白同样将自己的牌从左往右铺开
小梅对自己的牌从左到右进行N个回合的操作，生成一个新的牌序列， 每个回合操作有如下三种选择
1. d 取出一张牌 丢掉
2. l 取出一张牌 将他放在 新序列的左边
3. r 取出一张牌 将他放在 新序列的右边
当 新序列 = 小白的牌序列时， 小梅赢， 求 小梅能够获胜的所有的赢法
思路：
暴力解法
#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
string mei, bai;
void print_ans() {
cout << "{" << endl;
for (string& a : ans) {
for (char ch : a) {
cout << ch << " ";
}
cout << endl;
}
cout << "}" << endl;
}
void solve(int cur, string ret, string choice) {
if (cur == mei.size()) {
if (ret == bai) ans.push_back(choice);
else return;
} else {
solve(cur + 1, ret, choice + 'd');
solve(cur + 1, ret + mei[cur], choice + 'r');
solve(cur + 1, mei[cur] + ret, choice + 'l');
}
}
int main() {
int cnt;
cin >> cnt;
while (cnt--) {
cin >> mei >> bai;
ans.clear();
solve(0, "", "");
sort(ans.begin(), ans.end());
print_ans();
}
return 0;
} 第三题
n * m 的宫格 ， 其中 位置 (i, j) 方格的值为 i * j
将 宫格中的数字降序排序，给定 数字 k , 求该降序序列中第k 个数字的值
举例
n = 3, m = 3, k = 3, 宫格长这样
1 2 3
2 4 6
3 6 9
排序后 {9, 6, 6, 4, 3, 3, 2, 2, 1}
k = 3时 输出 6
AC 30% ，据说能用二分法解，不会，请大佬解答！
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> pq;
int n, m, k;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
pq.push(i * j);
}
}
for (int i = 1; i < k; ++i) pq.pop();
int ans = pq.top();
cout << ans << endl;
return 0;
} 
投递腾讯等公司10个岗位 >
携程公司氛围 85人发布