面试题的题面是这样的:
给定一个二维数组,实现一个功能函数 fn,向这个函数中传递这个二维数组的一个坐标,如果这个坐标的值为 ”1“,将返回和这个坐标所有相连的并且坐标值为1坐标。例如,传递了 fn([3,4])得到的结果为:[[3,4],[4,4],[5,4],[6,4],[7,4],[8,4],[8,5],[8,6]]。二维数组代码如下:
var arr =[
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,1,0,0],
[0,0,0,0,1,0,0,0,1,0,0],
[0,0,0,0,1,0,0,0,1,0,0],
[0,0,0,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0],
] ;
大家仔细看一下这个二维数组,这不就是消消乐的dom元素布局映射吗。点击这个数组的某一点,得到其坐标值,然后将与其相连,并且颜色相等的所有坐标都获取出来,改变其颜色,不就达到了消消乐的目的吗。
实现代码如下:
function doit([x,y]){
// 定义四个方向:
var queue = [[x,y]];
var direction = [
[-1,0],
[1,0],
[0,-1],
[0,1]
]
// 定义一个存储对象
var arrobj = arr.map(a=>a.map(e=>false))
while(queue.length>0){
// 循环一次去除一项,这便是核心了
var [x,y ] = queue.pop();
console.log(x,y)
console.log(arr[x][y])
// 循环四个方向上下左右,将与其值相等的坐标存入数组,并标记,
// 此处变动一下就是扫了的核心算法了扫雷是周围所有斜着相连的也计算在内
for(var i = 0;i<direction.length;i++){
var newx= x+direction[i][0];
var newy = y+ direction[i][1];
if(arr[newx][newy]==1&&arrobj[newx][newy]==false){
queue.push([newx,newy]);
arrobj[newx][newy] = true
}
}
}
// 定义结果数组
var result = [];
// 循环遍历从存储对象中将结果取出来
for(var i=0;i<arrobj.length;i++){
for(var j=0;j<arrobj[i].length;j++){
if(arrobj[i][j]==true){
result.push([i,j])
}
}
}
return result
}
var t =doit([3,4]);
console.log(t)
代码详解见注释。算法的问题任何语言都可以解决,主要是理解算法的核心思想。解题函数中初始化定义了一个存储对象和四个方向的数组,通过参数拿到一个坐标,循环遍历与这个坐标相连的四个方向上坐标,也就是上下左右四个坐标。在这个过程中得到的坐标肯定有重复的,所以就用到了一个存储对象,每次循环一个方向得到满足条件的坐标,就在存储对象上面标记一下,下次重复的话就不去处理。循环完成就得到了所有坐标。
点击原文链接查看更多的解题方法,如果你有好的方法或问题,欢迎留言。