算法 宽度遍历（面试题详解）

问题来源

https://segmentfault.com/q/1010000013091395?_ea=3284779

问题描述：

存在一个0，1值的二维数组，给定一个坐标[x,y]，如果该坐标所代表的元素值为1，则返回该坐标所代表的元素相邻的所有值为1的元素坐标。

解题思路

对于这种查找元素这类题目，脑袋里的第一个想法就是应该使用遍历。然后选择使用何种遍历，由于这个查找元素是跟位置有关的，所以使用宽度遍历（宽度遍历的定义）最合适。

宽度遍历：宽度优先遍历，是以离初态距离为序进行遍历。

解题方案

初始化定义：

• queue: 一个临时的缓存队列，存储临时匹配的结果
• result： 一个结果数组，存储所有的匹配结果
• memo：一个原数组的元素的记忆数组，如果存在记忆为true，初始值全为false

// 定义一个遍历数组
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]) {
    // 定义一个缓存队列queue，存储临时匹配的结果
    const queue = []
    // 定义一个result，存储所有的匹配结果
    const result = []
    // 定义一个原数组的元素的记忆数组，初始值为false，如果原数组的元素元素存在则记忆值变为true，
    const memo = arr.map(row => new Array(row.length).fill(false))
    // 定义一个方向数组，它的元素值分别表示左、右、上、下
    const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    // 如果指定位置元素值不为1，直接返回false，跳出查询函数;
    // 如果存在，则将位置结果推入临时数组queue，和结果数组result
    if (arr[x][y] !== 1) {
        return false
    } else {
        queue.push([x, y])
        result.push([x, y])
    }

    // 临时存储结果数组中是否有元素，如果有，则进行循环；如果没有，则跳出while循环，执行其它语句
    while(queue.length > 0) {
        // 从缓存队列中取出存在元素的坐标
        const [x, y] = queue.pop()
        // 查找该坐标位置左右上下位置值为1的元素，如果存在且记忆数组没有记忆过该元素，那么就将用memo记忆该元素，
        // 然后推入临时数组queue和结果数组，然后结束本次循环，接着返回循环条件判断，看是否接着执行循环，如果执行条件满足，重复循环体内的执行语句
        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
}

fn([3, 4])

根据JavaScript的特性，可以对算法进行优化，对于上例的记忆数组，我们可以使用对象来处理，这样可以减小初始化的开销。代码如下：

function fn([x, y]) {
    var memo = {}, // 将记忆数组改为记忆对象
        queue = [],
        result = [],
        direction = [[-1, 0],[1, 0],[0, -1],[0, 1]]

    if (arr[x][y] !== 1) {
        return false
    } else {
        queue.push([x, y])
        result.push(memo[x + "," + y] = [x, y])
    }

    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]) {
                queue.push([newX, newY]);
                result.push(memo[x + "," + y] = [newX, newY]);
            }
        })
    }
    return result;
}

当然，对于遍历如果我们使用递归方法的代码的书写量将会减少不少。可以将代码修改如下：

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

好了，今天宽度遍历算法的就先说到这里，后续可能还会继续修改，也欢迎各位批评指正。有问题或者有其他想法的可以在我的GitHub上pr。