基于C++的拼多多算法在线笔试题示例

2023-09-26 11:28:08 62

本文实例讲述了基于C++的拼多多算法在线笔试题。分享给大家供大家参考，具体如下：

最近在狼厂实习中，很久没做题了。秋招第一发，拼多多。。。四个简单题，看到有些人竟然觉得难？我来降一发自己的RP，这题目觉得难的，如果你拿到比我好的Offer，我是不服气的。。

四个题。。。其实我也就写了40分钟吧。。不过最后也没有满分，390/400，第三题不知道为嘛一直有10分过不了。。

更一下,刚刚好像发现第三题。。。这个>号，我写的是>=....?可是我看题目好像是>=呀。。。

第一题:

要求时间复杂度O(n)，空间复杂度O(1)。

那么其实答案有两种情况，最大的三个数相乘||最小的两个数*最大的数。时间复杂度O(n)，瞬间想到时间复杂度O(n)求k大的经典算法，分治法！

#include
#include
#include
#include
usingnamespacestd;
constintN=1e6+10;
longlonga[N];
intk;
intpartition(intl,intr){
while(l!=r)
{
while(a[r]>=a[l]&&r>l)
r--;
if(l==r)
break;
swap(a[r],a[l]);
while(a[l]l)
l++;
if(lnow)
returnsolve(now+1,r);
else
returna[now];
}
intmain(){
intn;
while(~scanf("%d",&n)){
for(inti=0;i3){
k=0;
longlongy1=solve(0,n-1);
k=1;
longlongy2=solve(0,n-2);
Ans=max(Ans,y1*y2*x1);
}
printf("%lld\n",Ans);
}
return0;
}

第二题:

大数相乘，模板题，找了个模板。。。

#include
#include
#include
#include
usingnamespacestd;
constintN=1e5+10;
stringc1,c2;
inta[N],b[N],r[N];
voidsolve(inta[],intb[],intla,intlb){
inti,j;
for(i=0;i!=N;i++)r[i]=0;
for(i=0;i!=la;i++)
{
for(j=0;j!=lb;j++)
{
intk=i+j;
r[k]+=a[i]*b[j];
while(r[k]>9)
{
r[k+1]+=r[k]/10;
r[k]%=10;
k++;
}
}
}
intl=la+lb-1;
while(r[l]==0&&l>0)l--;
for(inti=l;i>=0;i--)cout<>c1>>c2)
{
intla=c1.size(),lb=c2.size();
for(inti=0;i!=la;i++)
a[i]=(int)(c1[la-i-1]-'0');
for(inti=0;i!=lb;i++)
b[i]=(int)(c2[lb-i-1]-'0');
solve(a,b,la,lb);
}
return0;
}

第三题：

贪心啊，我是按照尽量满足最小人的需求来贪心的。。。一直90%? 有人是用尽量使用掉最大的巧克力来贪的，100%，来个反例好不好？

#include
#include
#include
#include
usingnamespacestd;
constintN=3e6+10;
longlongw[N],h[N];
intmain(){
intn,m;
while(~scanf("%d",&n)){
for(inti=0;i=h[i]){
++Ans;
++i,++j;
}
else{
++j;
}
}
printf("%d\n",Ans);
}
return0;
}

第四题：

迷宫问题，有趣的是多了一把钥匙。。。一看门不超过10个。。。M,N<=100...想了想状态数。。。直接状态压缩吧。。之后就是一个非常暴力可耻的状态压缩bfs。。。然后就一发AC了。。

#include
#include
#include
#include
#include
#include
usingnamespacestd;
constintN=110;
charmz[N][N];
boolvis[N][N][N*10];
intfx[4]={0,0,1,-1};
intfy[4]={1,-1,0,0};
intm,n;
mapkey;
structnode{
intx,y,cnt,sta;
node():cnt(0),sta(0){}
};
queueque;
intbfs(intsx,intsy,intex,intey){
while(!que.empty())que.pop();
nodetmp;
tmp.x=sx,tmp.y=sy;
que.push(tmp);
while(!que.empty()){
nodep=que.front();
if(p.x==ex&&p.y==ey){
returnp.cnt;
}
que.pop();
for(inti=0;i<4;++i){
intnewx=p.x+fx[i];
intnewy=p.y+fy[i];
if(newx<0||newx>=m||newy<0||newy>=n)continue;
if(mz[newx][newy]=='0')continue;
intsta=p.sta;
if(mz[p.x][p.y]>='a'&&mz[p.x][p.y]<='z'){
sta|=(1<='A'&&mz[newx][newy]<='Z'){
if((sta&(1<<(key[mz[newx][newy]-'A'+'a'])))==0){
continue;
}
}
vis[newx][newy][sta]=true;
tmp.x=newx,tmp.y=newy,tmp.cnt=p.cnt+1,tmp.sta=sta;
que.push(tmp);
}
}
return-1;
}
intmain(){
while(~scanf("%d%d",&m,&n)){
intsx,sy,ex,ey;
intcnt=0;
for(inti=0;i='a'&&mz[i][j]<='z'){
key[mz[i][j]]=cnt++;
}
}
}
for(inti=0;i
希望本文所述对大家C++程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

基于C++的拼多多算法在线笔试题示例

热门推荐

随机推荐