javascript二维数组的面试题
程序员文章站
2022-03-08 20:45:40
...
本文主要和大家分享一个关于javascript二维数组的面试题,希望能帮助到大家。给定一个二维数组,实现一个功能函数 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], ] ;
解答思路:宽度优先遍历即可。供参考,相连条件没给出且当做是横竖方向:
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], ] function fn ([x, y]) { if (arr[x][y] !== 1) return false const queue = [[x, y]] const memo = arr.map(row => new Array(row.length).fill(false)) const direction = [ [-1, 0], [1, 0], [0, -1], [0, 1], ] while(queue.length > 0) { const [x, y] = queue.pop() direction.forEach(([h, v]) => { const newX = x + h const newY = y + v if (arr[newX][newY] === 1 && !memo[newX][newY]) { memo[newX][newY] = true queue.push([newX, newY]) } }) } const result = [] for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr[i].length; j++) { if(memo[i][j]) { result.push([i, j]) } } } return result } console.log(fn([3,4]))
借鉴前两位 对象+递归实现
function fn(point) { var memo = {}, result = [], direction = [[-1, 0],[1, 0],[0, -1],[0, 1]] function dg([x, y]) { result.push(memo[x + "," + y] = [x, y]); direction.forEach(([h, v]) => { const newX = x + h const newY = y + v if (arr[newX][newY] === 1 && !memo[newX + "," + newY]) { dg([newX, newY]); } }) } dg(point); return result; }由于queue只是临时存匹配结果的,还要出队列进行新一轮的匹配所以只要再用一个缓存队列存储过往匹配的成功数据即可,没有必要最后在进行遍历的必要。代码如下:
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], ] function fn ([x, y]) { if (arr[x][y] !== 1) return false const queue = [[x, y]] const result = [[x,y]] const memo = arr.map(row => new Array(row.length).fill(false)) const direction = [ [-1, 0], [1, 0], [0, -1], [0, 1], ] while(queue.length > 0) { const [x, y] = queue.pop() direction.forEach(([h, v]) => { const newX = x + h const newY = y + v if (arr[newX][newY] === 1 && !memo[newX][newY]) { memo[newX][newY] = true queue.push([newX, newY]) result.push([newX, newY]) } }) } return result }
相关推荐:
定义JavaScript二维数组采用定义数组的数组来实现_基础知识
以上就是javascript二维数组的面试题的详细内容,更多请关注其它相关文章!
上一篇: 为什么react需要绑定this
下一篇: 讲解 JS 内存管理机制及验证