面试题：网络连通性检查

2018/04/02去哪儿编程面试题2

题目

解读

其实，刚看到这题的时候我内心是拒绝的，题都看不懂….
然后一看时间，还有四十多分钟，还是好好看看吧
…
经过一番不懈努力的挣扎…终于看懂题了…
虽然没来的及调试答案，但是能看懂还是有一丢丢成就感的（学渣的满足点就是这么低）
大致题意：有n个点(N个节点)，再给出M对点，每对点是两两相连的，然后再给出Q对点，让你判断其中有几对是联通的…
是的，就是这么简单

嘻嘻 …

思路

思路嘞，就是把所有相连的点放进一个数组里面并去重（相当于一个联通的域），然后判断需要判断的两个点是否都在一个域里面。
使用数组对象的arr.indexOf(n)方法，包含返回索引，不包含返回-1。
所以如果两个数都存在的话，那么两个返回值的和一定大于等于0。
然后设置个值来存储次数。循环完毕就返回。
perfect~

代码

这个是整理之后的js代码，做题的话是基于C的，这里就不作接受数据了~~ 直接模拟

var N = 4, M  = 4;                        //这里无用，附和题意
var arrA = [[1,2], [2,1], [3,2], [1,0]];  //M对点
var arrB = [[1, 2], [3, 0]];              //Q对点

function getRes(arrA, arrB) {
    var arr = [];
    for (var i = 0; i < arrA.length; i++){
        arr = [...arr, ...arrA[i]]
    }
    arr = [... new Set(arr)];    //去重
    function getQ(arr) {
        var res = 0;
        for (var j = 0; j < arrB.length; j++){
            if (arr.indexOf(arrB[j][0]) + arr.indexOf(arrB[j][0]) >= 0){
                res++;
            }
        }
        return res;
    }
    return getQ(arr);
}
console.log(getRes(arrA, arrB))  //2

突然想起要是给的数形成了多个联通域怎么办呢？

this is a question …

局域网大概就是这么回事吧

三天后…

撞过n次墙，不停换思路，不停重写。。。
再回头看最先一版的答案，我真是太天真了
出题人：呵，你们这些年轻人….

这题的难点就在于要找出所有的联通域

思路：

递归
定义一个函数，参数为需要找出联通域的数组arr
在函数中，定义一个tempArr变量，并将arr中的第一个元素取出并赋值给tempArr[0]
进入while循环中
通过for循环遍历arr中的元素，并挨个与tempArr[0]中的元素做对比
一旦出现相同的元素，将含有相同元素的数组从arr中删除并添加到tempArr[0]中，并立即结束本次for循环体
再次重新循环遍历…
直到arr中不含有tempArr[0]中的相同元素，（说明与tempArr[0]是同一个域的元素已经全部找出）
结束while循环
判断arr中是否还有值
如果有，继续执行该函数，参数为处理后的arr，并将返回值连接给tempArr
如果没有，说明arr中的所有值都已被归到不同的域中
返回tempArr
由于是递归机制，所以返回的值将连接给上层函数的结果值 然后持续向上返回，直到返回到最外层函数，得到最终结果

demo：

function findNet(yArr) {
    /*数组是引用类型   这里防止全局变量被污染  重新赋值给新的变量*/
    let arr = [...yArr];
    let tempArr = [];
    tempArr[0] = arr.shift();
    /*
    * opyArr作用：判断经过一次循环之后arr数组是否还在发生变化
    * 如果有     说明还有相同元素的可能  继续循环遍历
    * 如果没有   说明arr中含有tempArr[0]中元素的元素已经完全被取出  退出循环
    * */
    let copyArr = [];
    while(copyArr.length != arr.length) {
       copyArr = [...arr];                        //进入循环的arr  对比值
        for(let i = 0; i < arr.length; i++) {
            if(!!~tempArr[0].indexOf(arr[i][0]) || !!~tempArr[0].indexOf(arr[i][1])) {
                tempArr[0] = [...tempArr[0], ...arr.splice(i, 1)[0]];   /*被截取出来的是一个二维数组*/
                break;      //如果存在 结束本次for循环
            }
        }
    }
    tempArr[0] = [...new Set(tempArr[0])];  //去重
    /*如果arr中还有值 说明还有没有测试完的值 继续调用该函数 并将返回值连接给本函数得到的已定型的tempArr*/
    if(arr.length) {
        return [...tempArr, ...findNet(arr)]
    } else {
        return tempArr;
    }
}
var testArr = [[0,1],[1,3],[3,4],[4,7],[8,9],[10,11]];
console.log(findNet(testArr))
/*结果
Array(3)
0:(5) [0, 1, 3, 4, 7]
1:(2) [8, 9]
2:(2) [10, 11]
*/

---

终极答案：

var testArrA = [[0,1],[1,3],[3,4],[4,7],[8,9],[10,11]];  //M对点
var testArrB = [[1,2], [3,0],[8,9],[7,3]];               //Q对点
/*
获取连接次数
参数一：给出的两两连接数组     （M对）
参数二：需要是否两两相连的数组 （N对）
*/
function getConnectTimes(connectArr,testArr) {
    /*整理出所有的域*/
    function findNet(yArr) {
        let arr = [...yArr];
        let tempArr = [];
        tempArr[0] = [...arr.shift()];
        let copyArr = [];
        while(copyArr.length != arr.length) {
            copyArr = [...arr];
            for(let i = 0; i < arr.length; i++) {
                if(!!~tempArr[0].indexOf(arr[i][0]) || !!~tempArr[0].indexOf(arr[i][1])) {
                    tempArr[0] = [...tempArr[0], ...arr.splice(i,1)[0]];
                    break;   
                }
            }
        }
        tempArr[0] = [...new Set(tempArr[0])];
        if(arr.length) {
            return [...tempArr, ...findNet(arr)]
        } else {
            return tempArr;
        }
    }
    /*获取连接次数  这个和上面的getRes思路一致*/
    function getTimes(domainArr, testArr) {
        var times = 0;
        for (var i = 0; i < testArr.length; i++){
            for (var j = 0; j < domainArr.length; j++){
                if (!!~domainArr[j].indexOf(testArr[i][0]) && !!~domainArr[j].indexOf(testArr[i][1])){
                    times++;
                    break;
                }
            }
        }
        return times;
    }
    return getTimes(findNet(connectArr),testArr);  //闭包
}
console.log(getConnectTimes(testArrA,testArrB))  // 3

温故知新

1.break和continue的区别

break是结束整个循环体，比如

console.log('break实例');
for (var i = 0; i < 4; i++){
    console.log('判断前的i',i);
    if (i == 1){
        console.log('break');
        break;
    }
    console.log('判断后的i',i);
}

结果：

结论：循环中遇到break，直接结束了整个循环体

continue是结束单次循环，实例：

console.log('continue实例');
for (var i = 0; i < 4; i++){
    console.log('判断前的i',i);
    if (i == 1){
        console.log('continue');
        continue;
    }
    console.log('判断后的i',i);
}

结果：

结论：循环体中遇到continue仅是结束了单次循环，但是之后的循环并不会被影响

2.关于数组的赋值

数组这个东西，一直有点迷
值传递还是引用？
深拷贝和浅拷贝？
知识量有点大 放在下一篇详解吧

3.用到的ES6语法

tempArr[0] = […tempArr[0], …arr.splice(i, 1)[0]]
//相当于
tempArr[0] = tempArr[0].concat(arr[i]);
arr.splice(i, 1);

let arr = […yArr]
//相当于 slice()没有参数截取整个数组
let arr = yArr.slice();
//相当于
let arr = [].concat(yArr);
//相当于
let arr = JSON.parse(JSON.stringify(yArr));

4.js中一些特殊符号的骚操作

!!~arr.indexOf(i)中的!!+~符号，返回是否包含指定字符
~是按位取反(二进制)，例：~-2 == 1 ~-1 == 0 ~0 == -1 ~1 == -2
这里结合indexOf的作用 再用!!将其转换为bool类型，就可以直接判断数组中是否包含指定元素了

取整|
用法：num|0, 例：1.8|0 == 1

字符串转数字+
var str='123'; typeof(str) //string typeof(+str) //number

总结

总的来说还是要熟练递归
虽然实际编程中用的比较少
但是挺能锻炼思维的灵活性的
另外还需要对闭包有所理解
面试中也会经常问到
以前也只会看看文章 什么是闭包

emmmmmmmmmm……. 等等
貌似又把回调和闭包整混了…….
又双叒叕再重新学习一遍吧…..
闭包回调 请听下下篇分解…

再说回来
无论是实际编程中还是这样的烧脑题，基础才是最重要的！
如果基础不扎实，阻碍真的会很多。