文档内容
华为机考，华为笔试，软件类，2020 年 8 月
19 日题目，超详细解答。
题目根据身边同学反映普遍较难，仔细看了一下题目其实也并不难，
因为都没有涉及比较复杂的算法，但是这次的题目都比较繁琐，写起
来比较费时间。
题目一
题目描述：
已知有一堆人排成M行N列，（M，N均大于等于10小于等于
1000），现在从这群人中挑选一些人出来。在这个M行N列的队伍中，
每个人对应一个坐标，从最左上角的（0,0）到右下角的（M-1，
N-1）。这些人还会进行一次报数，报数顺序是按照类似蜗牛壳形状的
顺时针方向由外圈像内圈报数，当报数的个位数为7且十位数为奇数
的人出列，按报数顺序输出这些人的坐标。
例如：如下图所示一个5行5列的队伍，按顺时针顺序从外到里报数，
其中17满足条件，因此需要输出17的坐标(1,1)输入和输出格式：
输入为行数M和列数N
10 10
1
输出为满足条件的坐标：
[[7,9],[1,1],[8,2],[7,5],[4,4]]
1
要注意输出时候有个坑，前面几组输出坐标后还会输出一个逗号分隔，
最后一组坐标之后不输出逗号，因此需要把最后一个满足条件的坐标
找出来，输出得时候不输出逗号。
第一题思路思路比较清晰，就是先创建一个M行N列纯0的数组，然后按照这个
顺时针的顺序走一遍下来，并给每个坐标位置赋值（值为这个位置报
数号）。然后把满足出列条件的报数的坐标输出即可。按照顺序走的
时候需要按照以下的顺序来走：
1. 如果该坐标的左边和上边位置已经报过数，且右边位置还未报数，则该位
置报数之后向右继续报数。
2. 如果该坐标的右边和上边位置已经报过数，且下边位置还未报数，则该位
置报数之后向下继续报数。
3. 如果该坐标的右边和下边位置已经报过数，且左边位置还未报数，则该位
置报数之后向下继续报数。
4. 如果该坐标的左边和下边位置已经报过数，且上边位置还未报数，则该位
置报数之后向上继续报数。
上面报数的意思其实就是给二维数组赋值的过程，需要注意的是首先要先
把最外圈的报数完，因为在进行判断的时候会查询这些坐标相邻外圈元素
的状态，如果不先把最外圈的报数，在后面访问时数组会越界。
第一题代码
#include
using namespace std;
int main()
{
int M,N;
cin >> M >> N;
int sum0=M*N;//从后往前找找最后一个满足条件的计数。
while(sum0>0)
{
int r1 = sum0 % 100;
int x1 = r1 % 10;
r1 = r1 / 10;
int x2 = r1;
if(x1==7&&x2%2==1)
break;
sum0--;//sum0此时为最后一个满足条件的计数
}
int a[M][N];
for (int i0 = 0; i0 < M; i0++)
for (int j0 = 0; j0 < N; j0++)
a[i0][j0] = 0;int count = 1;
int i = 0, j = 0;
cout << '[';
while (a[i][j] == 0)
{
a[i][j] = count;
count++;
int s0 = a[i][j];
int r0=s0%100;//除以100的余数为后两位数，用r0记录。
int y1 = r0 % 10;//y1为个位数
r0 = r0 / 10;
int y2 = r0;//y2为十位数
if(y1==7&&y2%2==1)//满足条件的计数进行输出
{
cout << '[' << i << ',' << j << ']';
if(a[i][j]!=sum0)//最后一个复合条件的报数输出的时候单独处理，
不带逗号。
cout << ',';
}
if (i == 0 && j < N - 1)//先把最外圈的进行报数
j++;
else if (i == 0 && j == N - 1)
i++;
else if (i < M - 1 && j == N - 1)
i++;
else if (i == M - 1 && j == N - 1)
j--;
else if (i == M - 1 && j > 0)
j--;
else if (i == M - 1 && j == 0)
i--;
else if (i > 1 && j == 0)
i-- ;
else if (i == 1 && j == 0)
j++;
//开始内圈报数；
else if (a[i - 1][j]>0 && a[i][j - 1]>0 && a[i][j + 1] ==
0)
j++;
else if (a[i - 1][j]>0 && a[i][j + 1]>0 && a[i + 1][j] ==
0)i++;
else if (a[i + 1][j]>0 && a[i][j + 1]>0 && a[i][j - 1] ==
0)
j--;
else if (a[i +1][j]>0 && a[i][j - 1]>0 && a[i - 1][j] ==
0)
i--;
}
cout << ']';
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69运行结果：
调试过程中记录队伍报数编号的矩阵：
题目二
题目描述
给定二叉树每个节点的深度，计算多少种满足条件的二叉树。根节点
深度为0.
输入描述：
第一行为一个整数N，表示二叉树节点的数量,在1到1000之间。
第二行为N个整数，d1,d2,……dN表示每个节点的深度。
输出描述：
输出为满足条件的二叉树数量。由于结果可能非常大，因此输出为实
际结果除以（10^9+7）之后的余数。
例：
输入：
4
1 0 2 2
1
2输出：
2
1
例子解读：
上面的输入表示深度为1的节点有一个，深度为0的节点有一个，深
度为2的节点有两个。对应的两种二叉树的形状如下图所示：由答案
为2可以知道该题目不区分元素的不同，只根据二叉树的形状进行分
类。如果考虑元素分布的话，下图中D2-1和D2-2交换位置则又多了
一倍的种类，因此此题目只考虑多少种形状的二叉树即可，即只考虑
组合不考虑排列。第二题思路
该题如果高中排列组合学的比较好的话应该比较容易想到思路，理清
了数学关系这道题目就很简单了。
首先要根据输入把二叉树每层多少个节点数目统计好。例如
D0,D1,D2……DN分别表示第0层，1层，……N层的节点数目。对于
第i层，该层有Di个节点，则第i+1层有2Di个位置，因此需要从2Di
个位置中选D(i+1)个位置进行放置，则放置方法有
种。然后把所有层的放置方法数全部乘起来就得到最后总的不同形状
二叉树数量。
如上面的例子：第0 1 2层的节点数为1 1 2.因此对于第一层，有2个
位置选一个有2种选取方法，对于第2层，从2个位置选两个有1种
选择方法，因此总方法有2*1=2种方法，也就是两种不同形状的二叉
树。
第二题代码
#include
#include
using namespace std;
int zuhe(int m, int n)//定义计算组合数的函数
//组合数计算公式：m个里面选n个，结果为m!/((m-n)!n!)=(m*(m-1)*...(m-
n+1))/(n*(n-1)*...1);
//使用(m*(m-1)*...(m-n+1))/(n*(n-1)*...1)计算比m!/((m-n)!n!)能节省较
多的运算量。
{
int m0 = 1, n0 = 1;//m0,n0表示组合数计算中的分子和分母。
for (int i = 0; i < n;i++)
{
m0 = m0 * (m - i);
n0 = n0 * (n - i);
}
return m0 / n0;
}
int main(){
int N;
cin >> N;
int di;
int a[N] = {0};//用a[N]来记录每层的节点个数，初始化为0，后面每输入一个在
对应的层数加1.
int depth = 0;//depth记录二叉树深度（层数），N个节点的二叉树深度小于N，
for (int i = 0; i < N;i++)
{
cin >> di;
a[di]++;
if(di>depth)
depth = di;
}
long long count = 1;//记录总方法数，为二叉树各层组合数的乘积。结果可能比
较大，使用longlong类型。
int cmn;
for (int i = 1; i <= depth;i++)
{
cmn = zuhe(2 * a[i - 1], a[i]);//调用组合函数计算每层有多少种组合方
法。
count = count * cmn;
}
int r0 = pow(10, 9) + 7;//pow默认返回值为double，这里转为int类型方便下
面求余运算。
int ans=count%r0;
cout << ans;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12 13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
运行结果：
题目三题目描述
俄罗斯方块，输入有两个字符串，第一个frame表示当前底座状态，
第二个brick表示下落方块的状态，下落的方块只能左右移动不会旋转。
方块落下后如果一行全部充满则会消失，最后求最少还剩多少行。输
入的底座和方块都不超过9列，即最大只有9列。
例如：
输入为：
2122
121
1
2
底座和方块状态如下图所示：其中2122表示当前底座状态，都是底对
齐的，而121表示下落方块的状态，都是顶对齐的，即2的位置的突
出是往下凸而不是往上凸。下图运行结果为1，下图中方块左右移动有
两种下落方式，一种如下图所示，下落后会消去两行最后剩余1行。
另外一种下落方式是向又移动一格然后再下落，最后消去一行剩余3
行，因此最少的结果是剩余1行，输出为1
输出为：
1
1第三题思路
该题思路非常简单，把方块从左到右依次落下并记录剩余的行数，取
行数最小的输出。但写起来较为繁琐，关键是如何表示方块。可以用
一个二维数组来表示。如上面的例子，共有两种下落方法，一种是靠
左边，此时将各列相加可得到3332.
1 2 1
2 1 2
3 3 3
注意方块下落所在的三列，高度都为3，和方块的顶对齐保持一致。说
明这些列下方没有空格。如下图所示：而靠右边下落的情况，将各列相加得2243。
1 2
2 1 2
2 2 4
注意方块下落所在的三列高度分别为243，不满足方块的顶部对齐条
件。因此除了高度最高的那列之外，剩下的俩列都有空格，高度为2
的有两个空格，高度为3的有一个空格。如下图所示：在处理中需要
特别注意。另外输入的是字符串，需要把每个单独转化为数字处理。
第三题代码
#include
#include
using namespace std;
int main()
{
string frame;string brick;
cin >> frame>>brick;//输入底座和掉落的方块。
int framelen = frame.size();//求底座列数
int bricklen = brick.size();//求方块列数
int leftmin = 10000;//表示剩余最小行数，初始为一个较大的数。
int frame0[framelen], brick0[bricklen];//将输入的字符串转为数字保存到整
型数组中。
for (int i = 0; i < framelen;i++)
frame0[i] = frame[i] - '0';//因为列数小于9，减去0的ascii值即可将
字符串转为响应的数字。
for (int i = 0; i < bricklen;i++)
brick0[i] = brick[i] - '0';
int num = framelen - bricklen + 1;//左右移动方块共有num种掉落方法。
for (int i = 0; i < num;i++)
{
int frameadd[framelen];
for (int j = 0; j < framelen;j++)
frameadd[j] = frame0[j];
int height = 0;
for (int j = i; j < i + bricklen; j++)
{
frameadd[j] = frameadd[j] + brick0[j-i];
if(frameadd[j]>height)
height = frameadd[j];//height记录方块所在列的最高高度。
}
int framefin[framelen][height];//使用二维数组framefin记录方块下落
后的状态。
for (int j1 = 0; j1 < framelen;j1++)
for (int j2 = 0; j2 < height;j2++)
framefin[j1][j2] = 0;//先初始为全0；
for (int j1 = 0; j1 < framelen;j1++)
for (int j2 = 0; j2 < frame0[j1];j2++)
framefin[j1][j2] = 1;//先把下落前的底座用1填充。
for (int j1 = i; j1 < i + bricklen;j1++)
{
int num0 = height - frameadd[j1];//num0记录砖块和基座之间的空格
数目。
for (int j2 = frame0[j1] + num0; j2 < height;j2++)
framefin[j1][j2] = 1;//跳过空格然后再填充1，空格数为最高的高
度减去当前列高度。
}//下面进行判断消去的多少行，每消去一行height-1，最后剩余的行数为
height。
int height0 = height;
for (int j2 = 0; j2 < height0;j2++)//这个地方单独定义一个height0控
制循环次数，因为height在循环体内会改变，如果还要用height，循环次数会变化。
{
int flag = 1;//如果j1行不全为1，则改变flag的值。
for (int j1 = 0; j1 < framelen;j1++)
{
if(framefin[j1][j2]==0)
{
flag = 0;
break;
}
}
if(flag==1)//如果flag未改变，则表明这一行全为1，则消去一行
height--;
}
if(height
