基于基于C++的拼多多算法在线笔试题示例的拼多多算法在线笔试题示例
本文实例讲述了基于C++的拼多多算法在线笔试题。分享给大家供大家参考,具体如下:
最近在狼厂实习中,很久没做题了。秋招第一发, 拼多多。。。 四个简单题,看到有些人竟然觉得难? 我来降一发自己的
RP,这题目觉得难的,如果你拿到比我好的Offer,我是不服气的。。
四个题。。。其实我也就写了40分钟吧。。不过最后也没有满分, 390/400, 第三题不知道为嘛一直有10分过不了。。
更一下, 刚刚好像发现第三题。。。这个>号, 我写的是>= ….? 可是我看题目好像是 >= 呀。。。
第一题第一题:
要求时间复杂度O(n), 空间复杂度O(1)。
那么其实答案有两种情况,最大的三个数相乘 || 最小的两个数 * 最大的数。 时间复杂度O(n),瞬间想到时间复杂度O(n)求k大
的经典算法,分治法!
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
long long a[N];
int k;
int partition(int l,int r) {
while(l != r)
{
while(a[r] >= a[l] && r > l)
r--;
if(l == r)
break;
swap(a[r],a[l]);
while(a[l] < a[r] && r > l)
l++;
if(l < r)
swap(a[r],a[l]);
}
return l;
}
long long solve(int l,int r) {
int now = partition(l,r);
if(k < now)
return solve(l,now-1);
else if(k > now)
return solve(now+1,r);
else
return a[now];
}
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
k = n - 1;
long long x1 = solve(0, n-1);
k = n - 2;
long long x2 = solve(0, n-2);
k = n - 3;
long long x3 = solve(0, n-3);
long long Ans = x1 * x2 * x3;
if(n > 3) {
k = 0;
long long y1 = solve(0, n-1);
k = 1;
long long y2 = solve(0, n-2);
Ans = max(Ans, y1*y2*x1);
}
printf("%lld\n", Ans);
}
return 0;
}
第二题第二题: