算法 宽度遍历(面试题详解)

简介: 问题来源https://segmentfault.com/q/1010000013091395?_ea=3284779问题描述:存在一个0,1值的二维数组,给定一个坐标[x,y],如果该坐标所代表的元素值为1,则返回该坐标所代表的元素相邻的所有值为1的元素坐标。

问题来源

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。

相关文章
|
14天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
17天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
44 5
|
17天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
22 2
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
20天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
24 0
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
33 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
1月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
74 2
|
1月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0

热门文章

最新文章

下一篇
无影云桌面