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

简介: 问题来源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。

相关文章
|
3月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
14天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
20天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
28 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
8天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
14天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
22天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
50 2
|
20天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
16 0
|
2月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
3月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
|
3月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!