华为7.14机试回顾
简单说一下大家可能会关注的考试要求相关的小问题：
1.考试过程中可以用草稿纸，可以上厕所(建议跑步来回)。
2.可以使用本地IDE，但是我在本地调试完发现粘贴不过来了，最后只能重新手动输入(浪费时间，第一次还输错了==！)
3.如果出现什么自己不好把握的问题，可以咨询答题页面下方的工作人员，回复很快的。
4.考试全程摄像头开启，屏幕共享，我在切换到IDE时还是被提醒了一次(不知为何，当时吓了一跳)
考试题目
1.蜂巢形状的区域相连(M*N)，输入中只有C(Clean)和P(Pollution)两种数据，要求输入未被污染的区域数量
当时看到这个题第一反应就是dfs，本来准备这次考试用c来写，但是在写动态数组的时候脑子死活无响应，硬着头皮写了c++，由于好久都不编程了，很多东西都忘了，花了一个小时才调出来。
思路大概就是：所有的点只要是C就dfs一次，每次dfs过程中把能扩展到的C点都变成P，最后用res记录总共把多少片区域从C变成了P；这道题AC了
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
void dfs(vector< vector<char> > & grid,int x,int y,int m, int n)
{
if(x>=0 && x<m && y>=0 &&y<n)//没有出界
{
if(grid[x][y]=='C')
{
grid[x][y]='P';
dfs(grid,x-1,y,m,n);//上
dfs(grid,x-1,y+1,m,n);//右上
dfs(grid,x,y+1,m,n);//右
dfs(grid,x,y-1,m,n);//左
dfs(grid,x+1,y-1,m,n);//左下
dfs(grid,x+1,y,m,n);//下
}
}
}
int solve(vector< vector<char> >&grid)
{
int res = 0;
int m = grid.size(),n = grid[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]=='C')
{
dfs(grid,i,j,m,n);
res++;
}
}
}
return res;
}
int main()
{
int m,n;//m行 ，n列
cin>>m>>n;
vector< vector<char> >hive;
for(int i=0;i<m;i++)
{
vector<char> *a = new vector<char>();
hive.push_back(*a);
for(int j=0;j<n;j++)
{
char c;
cin>>c;
hive[i].push_back(c);
}
}
cout<<solve(hive);
return 0;
} 2.推箱子游戏，看到这个题目的时候，我脑海里第一画面是我初中拿着小灵通坐在灶坑边上玩推箱子游戏的场景。。。
题目大概是给一组长度为N的整数字符串，每个箱子最终的位置，要求是把所有箱子都从0推到最终位置，允许连续的箱子一起推，比如2，3，4号箱子都需要前进的话，推一次就可以，输出最少的推动次数。
我在纸上比划了半天，一开始想到的是分割，递归。但是题里给的N<100000;感觉不太行，就在纸上反复的画，最终想到一个办法，由于时间限制最终就调出来90%，没时间了交卷了就。
思路：题目里要求从0推到最终位置，我想的是把他们从最终位置推回来，而我在反复写最终位置的序列时，想到如果一个位置比它相邻位置大的话，那不论是单独推，还是同时推，总要多推那么一下才能把这个箱子归位，于是求出每个位置的差，然后把其中正的值都加起来，不就是需要的次数了么。而且一下子复杂度就下来了。
代码及其简单。
#include <stdio.h>
int main()
{
int c;
int a[100005]={ 0 };
int b[100005]={ 0 };
int i,j=1;
while(scanf("%d",&c)!=EOF)
{
a[j] = c;
j++;
if(c<0 || c>100000)
{
printf("-1");
return 0;
}
}
for(i=1;i<100005;i++)
{
b[i] = a[i] - a[i-1];
}
int sum = 0;
for(i=1;i<100005;i++)
{
if(b[i]>0)
{
sum += b[i];
}
}
printf("%d",sum);
return 0;
} 3.原谅我弱鸡的本质，只能帮你们回忆一下题了。
网络维护：在一个n个结点的网络中，每个结点i的吞吐量为2^i，由于缺电(可能是湾湾)需要关闭其中的k个结点，需要保证剩余结点仍能互通，输入就是n和k两个值，空格隔开，输出要求给出关闭的结点顺序，升序排列。n<100000好像是。
#互联网求职##学习路径#
投递华为等公司10个岗位