华为八月份机试题总结1-0804
对题目进行了详细的描述，并提供了输入输出示例，参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习，offer拿到手软！！！
第三题没找到具体的输入输出，希望考过的大佬补充一下细节
感觉和leetcode的652有点相似
感觉和leetcode的652有点相似
/*
华为的机试题0804-1：
题目： 岛屿的最大面积
输入：
3 4 //注意是列和行
0 0 0
1 1 0
0 0 1
1 1 1
输出：4
*/
#include<bits/stdc++.h>
using namespace std;
int dfs(vector<vector<int>> &graph, int i, int j)
{
if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j] == 0)
{
return 0;
}
graph[i][j] = 0;
return 1 + dfs(graph, i+1, j) + dfs(graph, i-1, j) + dfs(graph, i, j+1) + dfs(graph, i, j-1);
}
int main()
{
int max_area=0;
int row, col;
cin>>col>>row;
vector<vector<int>> graph(row, vector<int>(col, 0));
for(int i=0; i<row; i++)
{
for(int j=0; j<col; j++)
{
int a;
cin>>a;
graph[i][j] = a;
}
}
for(int i=0; i<row; i++)
{
for(int j=0; j<col; j++)
{
if(graph[i][j] == 1)
{
int area = dfs(graph, i, j);
max_area = max(area, max_area);
}
}
}
cout<<max_area<<endl;
return 0;
}
/*
华为的机试题0804-2：
题目： 爬电梯从第N层到第M层。规则：只能向下一层一层的爬或向上N＊i的坐电梯。求从N到M的最小时间
输入：
5 7
输出：3
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N, M;
cin>>N>>M;
if(M<N) //因为向下只能一层一层的爬
{
cout<<N-M<<endl;
return 0;
}
//接下来考虑向上的情况dp[i]表示从N都第i层所花费的最少时间。
//因为最后往上只能是
vector<int> dp(M+1, 0); //便于和楼层对应，dp[0]不用
for(int i=1; i<=N; i++) // 小于等于N层的只能往下走，因此初始化为N-i
{
dp[i] = N-i;
}
for(int i=N+1; i<=M; i++) //大于N层的，只能做电梯
{
if(i%2==0) //直接做电梯一步到达
{
dp[i] = dp[i/2]+1;
}
else //先坐到i+1层，再往下走一层
{
dp[i] = dp[(i+1)/2]+2;
}
}
cout<<dp[M]<<endl;
return 0;
}
