大家好，又见面了，我是你们的朋友全栈君。
选择题很难做，阿里的秋招貌似非常难，大部分岗位都留给了实习生，但是两道编程题不怎么难。
第一题
有一个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;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/142331.html原文链接：https://javaforall.net
