2021阿里巴巴校招筆試真題_Java工程師、C++工程師_牛客網(wǎng)

1.小強(qiáng)現(xiàn)在有n個(gè)物品,每個(gè)物品有x,y兩種屬性和.他想要從中挑出盡可能多的物品滿足以下條件:對于任意兩個(gè)物品 i 和?j ,滿足（ i.x < j.x 且 i.y < j.y）或者（i.x > j.x 且 i.y > j.y）.問最多能挑出多少物品.

解：將物品按照x從小到大排序，x相同則y從小到大排序，將題目轉(zhuǎn)變?yōu)?#xff0c;尋找y的最長遞增子序列，LIS。實(shí)現(xiàn)時(shí)用dp時(shí)間復(fù)雜度是n^2，會(huì)超時(shí)。用二分是nlogn可以過。

LIS：遍歷數(shù)組，維護(hù)一個(gè)【遞增的數(shù)組】。當(dāng)a[i]大于數(shù)組的最后一個(gè)值則直接插入尾端，否則用二分查找該值插入的位置，取代第一個(gè)比他大的值。當(dāng)遍歷結(jié)束后，該數(shù)組的長度即為最長遞增子序列的長度。（ps：該數(shù)組不一定是最長遞增子序列的解哦~）

#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<string> #include<algorithm> #include<map> #include<queue> #include<vector> using namespace std;int B[1000005],len; struct p {int x,y; }a[100005];int cmp(p u, p w) {if(u.x!=w.x)return u.x<w.x;elsereturn u.y>w.y; } int BiSearch(int *b,int len,int w) { int left=0,right=len-1; int mid; while(left <= right) { mid=left+(right-left)/2; if (b[mid]>w) right=mid-1; else if (b[mid]<w) left=mid+1; else return mid; } return left; } int LIS(int *array,int n) { len=1;B[0]=array[0]; int i,pos=0; for(i=1;i<n;i++) { if(array[i]>B[len-1]) { B[len]=array[i]; len++; } else { pos=BiSearch(B,len,array[i]);B[pos]=array[i]; } } return len; } // 最長遞增子序列 int main() {int t,n,i,j;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i].x);for(i=0;i<n;i++)scanf("%d",&a[i].y);sort(a,a+n,cmp);int s[n];for(i=0;i<n;i++)s[i]=a[i].y;printf("%d\n",LIS(s,n));}}

2.小強(qiáng)發(fā)現(xiàn)當(dāng)已知xy=B以及x+y=A時(shí),能很輕易的算出的值.但小強(qiáng)想請你在已知?A和B的情況下,計(jì)算出x^n+y^n的值.因?yàn)檫@個(gè)結(jié)果可能很大,所以所有的運(yùn)算都在模1e9+7下進(jìn)行.

解：列出n項(xiàng)找遞推關(guān)系。

#include<stdio.h> long long mm = 1e9+7; long long p[100005]; int main() {int t,a,b,n,i,j; scanf("%d",&t);while(t--){scanf("%d%d%d",&a,&b,&n);p[0]=2,p[1]=a;for(i=2;i<=n;i++){p[i]=(a*p[i-1]%mm-b*p[i-2]%mm+mm)%mm;//printf("%d %d\n",i,p[i]);}printf("%lld\n",p[n]);} }

3.?小強(qiáng)現(xiàn)在n有個(gè)節(jié)點(diǎn),他想請你幫他計(jì)算出有多少種不同的二叉樹滿足節(jié)點(diǎn)個(gè)數(shù)為且樹的高度不超過m的方案.因?yàn)榇鸢负艽?所以答案需要模上1e9+7后輸出.
樹的高度: 定義為所有葉子到根路徑上節(jié)點(diǎn)個(gè)數(shù)的最大值.

解：N個(gè)結(jié)點(diǎn)二叉樹的個(gè)數(shù)是卡特蘭數(shù)，計(jì)算方法可以用遞歸思想得到，但這題還要增加一個(gè)高度限制。因此用二維數(shù)組來做dp。

可參考：組合數(shù)學(xué) 卡特蘭數(shù) 解釋與應(yīng)用_請賜教-CSDN博客

#include<stdio.h> long long dp[55][55]; long long mod = 1e9+7; int main() {int n,m,i,j,k;scanf("%d%d",&n,&m);for(i=0;i<=m;i++)dp[0][i]=1;for(i = 1; i <= n; i++) {for(j = 1; j <= m; j++) {for(k = 0; k < i; k++) {int aa = (dp[k][j-1] * dp[i-k-1][j-1])% mod;dp[i][j] += aa;dp[i][j] %= mod;}}}printf("%d\n",dp[n][m]); }

4.小強(qiáng)在玩一個(gè)走迷宮的游戲，他操控的人物現(xiàn)在位于迷宮的起點(diǎn)，他的目標(biāo)是盡快的達(dá)到終點(diǎn)。每一次他可以選擇花費(fèi)一個(gè)時(shí)間單位向上或者向下或者向左或者向右走一格，或是使用自己的對稱飛行器花費(fèi)一個(gè)時(shí)間單位瞬移到關(guān)于當(dāng)前自己點(diǎn)中心對稱的格子，且每一次移動(dòng)的目的地不能存在障礙物。

具體來數(shù)說，設(shè)當(dāng)前迷宮有n行m列，如果當(dāng)前小強(qiáng)操控的人物位于點(diǎn)A ( x , y )，那么關(guān)于點(diǎn)A中心對稱的格子B ( x ′ , y ′ )滿足x + x ′ = n + 1且y + y ′ = m + 1。需要注意的是，對稱飛行器最多使用5次。

解：廣搜四個(gè)方向+飛行器，注意標(biāo)記走過的路、飛行器的使用次數(shù)等，這題深搜會(huì)超時(shí)。

#include<stdio.h> #include<queue> #include<string> #include<algorithm> using namespace std; struct p{int x,y,c,t; //c飛行次數(shù) }; int fx[4][2]={0,1,0,-1,1,0,-1,0}; int a[505][505]; int main() {int n,m,i,j,k;int sx,sy,ex,ey;int mintime = 1e8;char c;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){ getchar();for(j=1;j<=m;j++){scanf("%c",&c);if(c=='.')a[i][j]=1;else if(c=='#')a[i][j]=-1;else if(c=='S')sx=i,sy=j;else if(c=='E')ex=i,ey=j,a[i][j]=1;}}queue<p> q;p start;start.x=sx;start.y=sy;start.c=5;start.t=0;q.push(start);a[sx][sy]=-1;while(!q.empty()){p now = q.front();//printf("now:%d %d %d %d\n",now.x,now.y,now.c,now.t);q.pop();if(now.x==ex&&now.y==ey){if(now.t<mintime)mintime=now.t;}for(i=0;i<4;i++){int nextx = now.x+fx[i][0];int nexty = now.y+fx[i][1];if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m&&a[nextx][nexty]==1){//printf("next:%d %d %d %d\n",nextx,nexty,now.c,now.t+1);a[nextx][nexty]=-1;p next;next.x=nextx;next.y=nexty;next.c=now.c;next.t=now.t+1;q.push(next);}}if(now.c!=0){int nextx = n+1-now.x;int nexty = m+1-now.y;if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m&&a[nextx][nexty]==1){//printf("fly:%d %d %d %d\n",nextx,nexty,now.c-1,now.t+1);a[nextx][nexty]=-1;p next;next.x=nextx;next.y=nexty;next.c=now.c-1;next.t=now.t+1;q.push(next);}}}if(mintime!=1e8)printf("%d\n",mintime);elseprintf("-1\n"); }

5.最近部門要選兩個(gè)員工去參加一個(gè)需要合作的知識(shí)競賽，每個(gè)員工均有一個(gè)推理能力值A(chǔ)i，以及一個(gè)閱讀能力值Bi。如果選擇第i個(gè)人和第j個(gè)人去參加競賽，那么他們在閱讀方面所表現(xiàn)出的能力為X=(Bi+Bj)/2，他們在推理方面所表現(xiàn)出的能力為(Ai+Aj)/2。現(xiàn)在需要最大化他們表現(xiàn)較差一方面的能力，即讓min(X,Y) 盡可能大，問這個(gè)值最大是多少。

解：將員工的A,B能力值之差的絕對值k=|ai-bi|由小到大排序，那么較差的能力是A還是B肯定是由排在后面的員工決定的。(原理：先取a,b中較小者，假設(shè)b<a，則b和max(b)的組合一定是當(dāng)前對該員工來說的最佳組合，且b是組合的弱項(xiàng)。因?yàn)閎的最好結(jié)果b+max(b) <= a+最大b員工的a項(xiàng)。即a-b>=最大b員工的(b-a)，即后者的k>前者的k，可對應(yīng)排序結(jié)果)

遍歷排序好的結(jié)構(gòu)體，將當(dāng)前員工的較弱能力（A/B）跟【當(dāng)前】（遍歷過程中記錄當(dāng)前的最值）該項(xiàng)能力（A/B）的最大值相加得maxk，記錄全局得maxk即為解。

#include<stdio.h> #include<math.h> #include<queue> #include<string> #include<algorithm> using namespace std; struct node{int a,b,k; }p[200005]; int cmp(node u,node w) {if(u.k!=w.k)return u.k<w.k;if(u.a!=w.a)return u.a<w.a;elsereturn u.b<w.b; } int main() {int n,i,j,k;int maxa=-1,maxb=-1,maxk=-1;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&p[i].a,&p[i].b);p[i].k=fabs(p[i].a-p[i].b);}sort(p,p+n,cmp);maxa=p[0].a;maxb=p[0].b;for(i=1;i<n;i++){if(p[i].a>p[i].b){if(p[i].b+maxb>maxk)maxk=p[i].b+maxb;}else{if(p[i].a+maxa>maxk)maxk=p[i].a+maxa;}if(p[i].a>maxa)maxa=p[i].a;if(p[i].b>maxb)maxb=p[i].b;}printf("%.1lf\n",maxk/2.0); }

總結(jié)

以上是生活随笔為你收集整理的牛客网笔试真题 2021 阿里巴巴编程题（4星）题解（1-5）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。