华为笔试,矩阵中5个数连通
题目描述:
给定一个5*5的矩阵,矩阵形式为
| 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 |
给定5个数,判断它们是否连通?
例:
输入: 3 11 12 13 23
输出: true
解决方法:
如果给定的5个数是相通的,那么它们相邻元素之差非1即10,所以可以排列组合
,使5个数中任意两数相减,考虑到输入数据是乱序的,所以相邻元素之差可能会出现1、-1、10和-10四种情况,直接判断相减结果中1、-1、10和-10的个数(count)是否为4个即可,如果是4个,那它们就是连通的,否则不连通。
2019.9.11 更正:
这种方法对于5个数中4个组成正方形时会出错,这种情形可分为两种情况:一种是组成正方形且连通,此时count==5 ;一种是组成正方形但不连通,此时count==4,如果直接根据count是否为4返回bool值,就会有一部分不连通的情况,但返回了true,对于这一情况,目前我还没有什么好的方法把它与其它连通情况分离,求教。
情形一
情形二
附C++代码:
#笔试题目##题解##C/C++##华为#bool isConnect(const vector<int>& nums) {
if (nums.size() != 5)
return false;
int result=0,count=0;
for (int i = 0; i < nums.size() - 1;++i)
for (int j = i + 1; j < nums.size(); ++j) {
result=nums[j]-nums[i];
if (result ==1||result==10||result==-1||result==-10)
++count;
}
if(count == 5) //对于5个数中4个组成正方形且连通的情况,count==5
return true;
if(count == 4) //等于4时,可能混有4个数组成正方形但不连通的情况
return true;
return false;
}