|
2021阿里巴巴校招笔试真题_Java工程师、C++工程师_牛客网
1.小强现在有n个物品,每个物品有x,y两种属性和.他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品 i 和?j ,满足（ i.x < j.x 且 i.y < j.y）或者（i.x > j.x 且 i.y > j.y）.问最多能挑出多少物品.
解：将物品按照x从小到大排序，x相同则y从小到大排序，将题目转变为，寻找y的最长递增子序列，LIS。实现时用dp时间复杂度是n^2，会超时。用二分是nlogn可以过。
LIS：遍历数组，维护一个【递增的数组】。当a[i]大于数组的最后一个值则直接插入尾端，否则用二分查找该值插入的位置，取代第一个比他大的值。当遍历结束后，该数组的长度即为最长递增子序列的长度。（ps：该数组不一定是最长递增子序列的解哦~）
#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;
else
return 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.小强发现当已知xy=B以及x+y=A时,能很轻易的算出的值.但小强想请你在已知?A和B的情况下,计算出x^n+y^n的值.因为这个结果可能很大,所以所有的运算都在模1e9+7下进行.
解：列出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.?小强现在n有个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为且树的高度不超过m的方案.因为答案很大,所以答案需要模上1e9+7后输出.
树的高度: 定义为所有叶子到根路径上节点个数的最大值.
解：N个结点二叉树的个数是卡特兰数，计算方法可以用递归思想得到，但这题还要增加一个高度限制。因此用二维数组来做dp。
可参考：组合数学 卡特兰数 解释与应用_请赐教-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.小强在玩一个走迷宫的游戏，他操控的人物现在位于迷宫的起点，他的目标是尽快的达到终点。每一次他可以选择花费一个时间单位向上或者向下或者向左或者向右走一格，或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子，且每一次移动的目的地不能存在障碍物。
具体来数说，设当前迷宫有n行m列，如果当前小强操控的人物位于点A ( x , y )，那么关于点A中心对称的格子B ( x ′ , y ′ )满足x + x ′ = n + 1且y + y ′ = m + 1。需要注意的是，对称飞行器最多使用5次。
解：广搜四个方向+飞行器，注意标记走过的路、飞行器的使用次数等，这题深搜会超时。
#include<stdio.h>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
struct p{
int x,y,c,t; //c飞行次数
};
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);
else
printf("-1\n");
}
5.最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值Ai，以及一个阅读能力值Bi。如果选择第i个人和第j个人去参加竞赛，那么他们在阅读方面所表现出的能力为X=(Bi+Bj)/2，他们在推理方面所表现出的能力为(Ai+Aj)/2。现在需要最大化他们表现较差一方面的能力，即让min(X,Y) 尽可能大，问这个值最大是多少。
解：将员工的A,B能力值之差的绝对值k=|ai-bi|由小到大排序，那么较差的能力是A还是B肯定是由排在后面的员工决定的。(原理：先取a,b中较小者，假设b<a，则b和max(b)的组合一定是当前对该员工来说的最佳组合，且b是组合的弱项。因为b的最好结果b+max(b) <= a+最大b员工的a项。即a-b>=最大b员工的(b-a)，即后者的k>前者的k，可对应排序结果)
遍历排序好的结构体，将当前员工的较弱能力（A/B）跟【当前】（遍历过程中记录当前的最值）该项能力（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;
else
return 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);
}
|