秋招机试（一）华为

    2019年8月28日晚，参加华为机试，结果不是太理想，勉强通过（大于100分即可），现将题目分享出来，供大家参考。

一、求直角三角形个数

题目描述

已知三角形周长，求满足该条件的直角三角形个数？

输入描述

整数p

输出描述

整数，表示直角三角形个数

题目分析

此题属于送分题，最直观思路，循环遍历所有值即可。

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(int p)
{
	int i_num = 0;
	for (int i = 1; i < p; ++i)
	{//直角长边
		for (int j = 1; j <= i; ++j)
		{//直角短边
			int i_z = (p - 1 - j)*(p - 1 - j);//斜边
			if ((i*i + j * j) == i_z)
				i_num++;
		}
	}
	return i_num;
}
int main()
{
	int i_p;
	cin >> i_p;
	cout << solution(i_p)<< endl;

    return 0;
}

运行发现超时啦！开始优化，思考直角三角形直角长边肯定小于周长的一半，短边肯定小于周长的三分之一，改进如下：

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(int p)
{
	int i_num = 0;
	for (int i = 1; i < p/2; ++i)
	{//直角长边
		for (int j = 1; j < p/3; ++j)
		{//直角短边
			int i_z = (p - 1 - j)*(p - 1 - j);//斜边
			if ((i*i + j * j) == i_z)
				i_num++;
		}
	}
	return i_num;
}
int main()
{
	int i_p;
	cin >> i_p;
	cout << solution(i_p)<< endl;

    return 0;
}

二、判断矩阵相邻元素

题目描述

一个5*5矩阵，输入6个元素，判断其是否相邻。

矩阵格式：

1 2 3 4 5

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

41 42 43 44 45

输入描述

1 2 3 4 5 11

12 13 14 23 45

输出描述

1

0

题目分析

此题最大的难度是读题，如果能读懂题目，做起来并不难，关键点就在于相邻的理解。话不多说，上代码，应该很好理解了。

判断两元素是否相邻：

bool isAdjacent(KPoint a, KPoint b)
{//判断两个数字是否相邻
	int i_distence = abs(a.x - b.x) + abs(a.y - b.y);
	if (i_distence == 1)
		return true;
	else
		return false;
}

用一个map存储输入矩阵，key为矩阵值，value为矩阵坐标。依次判断输入的六个数字是否有相邻元素，若每个元素均至少一个有相邻元素，则 

#include <bits/stdc++.h>

using namespace std;

struct KPoint
{
	int x;
	int y;
};
bool isAdjacent(KPoint a, KPoint b);

int main()
{
	map<int, KPoint> location;
	
	for (int i = 1; i <= 5; ++i)
	{//纵坐标变化
		for (int j = 1; j <= 5; ++j)
		{//横坐标变化
			KPoint point;
			point.x = j;
			point.y = i;
			int temp = (j - 1) * 10 + i;
			location[temp] = point;
		}
	}
	while (true)
	{
		vector<int> vec;
		for (int i = 0; i <= 5; ++i)
		{//输入六个点
			int x;
			cin >> x;
			vec.push_back(x);
		}

		//判断每个点是否都具有相邻点
		int flag = 0;
		for (int i = 0; i <= 5; ++i)
		{
			for (int j = 0; j <= 5; ++j)
			{
				KPoint a = location[vec[i]];
				KPoint b = location[vec[j]];
				if (isAdjacent(a, b))
				{//第i个数字与第j个数字相邻
					flag++;
					break;
				}
			}
		}
		if (flag == 6)//说明六个点均有相邻点，则元素必然相邻。
			cout << 1 << endl;
		else
			cout << 0 << endl;
	}
	
	system("pause");
	return 0;
}

bool isAdjacent(KPoint a, KPoint b)
{//判断两个数字是否相邻
	int i_distence = abs(a.x - b.x) + abs(a.y - b.y);
	if (i_distence == 1)
		return true;
	else
		return false;
}

三、求最长公共子序列长度

题目描述

输入A、B两个数组，两个数组内元素相同，仅排列顺序不同，假设A中删除N个元素，B中也删除相同元素后，AB完全一致。求N的最小值

输入描述

输入共三行，第一行为AB的元素个数，第二行为A的元素，第三行为B的元素，如：

5

1 2 3 4 5

2 3 4 5 1

输出描述

N的最小值

1

问题分析

仔细分析就会发现，此题实际上是求最长公共子序列的长度。