2020阿里笔试编程题[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

选择题很难做，阿里的秋招貌似非常难，大部分岗位都留给了实习生，但是两道编程题不怎么难。

第一题

有一个n*n的地图，一只兔子想要穿过这个地图，给出的地图是一个二维数组map[i][j]，数值表示该位置的毒雾持续时间，当兔子在（x,y）位置时，它可以跳到（x+2,y）或者（x,y+2）位置，跳的时候需要对应等待map[x+1][y]或者map[x][y+1]的时间，兔子开始跳的位置从map[1][1…n]中选择，兔子到达第n行或者跳到了第n+1行均表示闯过了，求出兔子最少要花多少时间。（6<= n <= 30）
示例：
输入
6
1,2,3,5,7,6
2,1,4,5,7,4
3,4,5,6,3,6
2,3,1,4,6,8
5,6,1,4,6,2
4,2,4,1,1,6
输出
6

分析

深搜即可，但是不知道我的代码能不能全部跑过，感觉是不怎么难，深搜的参数是坐标（x,y)，当y为n或n+1时记录当前时间，答案取最小时间即可。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
int n,ti,ans;
int mp[31][31];
int dfs(int x,int y)
{ 

if (x==n || x==n+1)
{ 

ans = min(ti,ans);
return 0;
}
ti += mp[x+1][y];
dfs(x+2,y);
ti -= mp[x+1][y];
if (y < n-1){ 

ti += mp[x][y+1];
dfs(x,y+2);
ti -= mp[x][y+2];
}
return 0;
}
int main()
{ 

cin>>n;
for (int i=1 ; i<=n ; i++){ 

for (int j=1 ; j<n ; j++){ 

scanf("%d,",&mp[i][j]);
}
scanf("%d",&mp[i][n]);
}
ans = INF;
for (int i=1 ; i<=n ; i++){ 

ti = 0;
dfs(1,i);
}
cout<<ans<<endl;
return 0;
}

第二题

有一群男孩（用’b’表示）和女孩（用’g’表示）围成了一个圈，这个圈由一串字符串给出，如bgbbbgg，这个字符串表示的圈中位置0是个男孩，位置6是个女孩，作为一个圈他们俩是挨着的。我们把身边女孩子特别多的男孩子称为快乐男孩，比如上面的位置0，他身边有三个女孩子，别的男孩子最多身边才俩女孩，所以这个是快乐男孩，现在想知道哪个是快乐男孩。
这题还有问题二，圈里连续的几个人被称为一个小团体，给出一个k，表示一个小团体里最多只能有k个女孩子，问这样的小团体里面最多能有几个男孩子？
示例
输入
bgbbbgbggbgbg
3
输出
6 6
示例解释：显然位置6的这个比身边有三个女孩子所以他是快乐男孩，bgbbb gbgg bgbg 小团体有三位女生和六位男生。

分析

这个模拟一下就好了，第一个问题找boy左右两边的girl的数量，往left遍历直到出现了新的boy，当left为0时下一个left为n-1，看一下当前left是否是初始boy，如果是说明圈里只有一个boy，可以不再往右边遍历，否则往right遍历直到出现了boy，当right为n-1时下一个right为0。
第二个问题先考虑女生数量少于等于k的情况，那么输出总共的男生数即可，否则，我的做法是先找到一个女生，这个女生不包括在小团体中，从这个位置往后算作小团体，数男生的数量和女生的数量，直到女生出现了k+1次的时候停止。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
string ss;
int k,happyboy,maxgirl,maxboy;
int main()
{ 

cin>>ss;
cin>>k;
int len = ss.length();
maxgirl = 0; maxboy = 0;
int le = 0,ri = 0,mov = 0;
int sumgirl = 0, sumboy = 0;
int gir = 0;
for (int i=0 ; i<len ; i++)
{ 

if (ss[i]=='b')
{ 

sumgirl = 0;
if (i==0) le = len-1;
else le = i-1;
if (i==len-1) ri = 0;
else ri = i+1;
while (ss[le]=='g')
{ 

sumgirl++;
if (le==0) le = len-1
else le--;
}
if (le != i){ 

while (ss[ri]=='g'){ 

sumgirl++;
if (ri==n-1) ri = 0;
else ri++;
}
}
if (sumgirl > maxgirl)
{ 

maxgirl = sumgirl;
happyboy = i;
}
}
else if (ss[i]=='g')
{ 

gir++;
}
}
if (gir <= k)
maxboy = len-gir;
else { 

for (int i=0 ; i<len ; i++){ 

int now = 0;
if (ss[i]=='g'){ 

sumboy = 0;
if (i < len-1) mov = i+1;
else mov = 0;
while (now < k)
{ 

if (ss[mov] == 'g'){ 

now++;
}
else { 

sumboy++;
}
mov++;
if (mov==len) mov = 0;
}
while (ss[mov]=='b'){ 

sumboy++;
mov++;
if (mov==len) mov = 0;
}
if (sumboy > maxboy)
{ 

maxboy = sumboy;
}
}
}
}
cout<<happyboy<<" "<<maxboy<<endl;
return 0;
}