一個(gè)關(guān)于javascript二維數(shù)組的面試題

題目是這樣的：
給定一個(gè)二維數(shù)組，實(shí)現(xiàn)一個(gè)功能函數(shù) fn，向這個(gè)函數(shù)中傳遞這個(gè)二維數(shù)組的一個(gè)坐標(biāo)，如果這個(gè)坐標(biāo)的值為 ”1“，將返回和這個(gè)坐標(biāo)所有相連的并且坐標(biāo)值為1坐標(biāo)。
例如,傳遞了 fn([3,4])得到的結(jié)果為：
[[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],
] ;

回答

編輯回答

礙你眼

@CRIMX 方法很棒！但是我想修改一點(diǎn)，由于queue只是臨時(shí)存匹配結(jié)果的，還要出隊(duì)列進(jìn)行新一輪的匹配所以只要再用一個(gè)緩存隊(duì)列存儲(chǔ)過(guò)往匹配的成功數(shù)據(jù)即可，沒(méi)有必要最后在進(jìn)行遍歷的必要。代碼如下：

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
}

@clm1100 如果對(duì)英文不排斥的話，推薦一個(gè)老外整理的很不錯(cuò)的JavaScript算法方面的GitHub項(xiàng)目

2018年2月17日 06:08

編輯回答

蔚藍(lán)色

借鑒前兩位對(duì)象+遞歸實(shí)現(xiàn)

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;
}

2017年7月20日 04:26

編輯回答

孤巷

謝邀，寬度優(yōu)先遍歷即可。供參考，相連條件沒(méi)給出且當(dāng)做是橫豎方向:

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]))

2018年3月1日 20:17