前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一道关于javascript二维数组的面试题

一道关于javascript二维数组的面试题

作者头像
挥刀北上
发布2019-08-06 16:35:52
7790
发布2019-08-06 16:35:52
举报
文章被收录于专栏:Node.js开发
这两天笔者在翻看以前写的一些代码,翻到笔者以前写的一个关于消消乐的小游戏,本来想写个游戏教程,但是涉及的代码量和内容量太大,所以就将其中的核心算法抽离了出来,并且将其核心算法编成了一道面试题发布到了网上,没想到浏览量还不少。

面试题的题面是这样的:

给定一个二维数组,实现一个功能函数 fn,向这个函数中传递这个二维数组的一个坐标,如果这个坐标的值为 ”1“,将返回和这个坐标所有相连的并且坐标值为1坐标。例如,传递了 fn([3,4])得到的结果为:[[3,4],[4,4],[5,4],[6,4],[7,4],[8,4],[8,5],[8,6]]。二维数组代码如下:

代码语言:javascript
复制
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],
] ;

大家仔细看一下这个二维数组,这不就是消消乐的dom元素布局映射吗。点击这个数组的某一点,得到其坐标值,然后将与其相连,并且颜色相等的所有坐标都获取出来,改变其颜色,不就达到了消消乐的目的吗。

实现代码如下:

代码语言:javascript
复制
function doit([x,y]){
    // 定义四个方向:
    var queue = [[x,y]];
    var direction = [
        [-1,0],
        [1,0],
        [0,-1],
        [0,1]
    ]
    // 定义一个存储对象
    var arrobj = arr.map(a=>a.map(e=>false))
    
    while(queue.length>0){
        // 循环一次去除一项,这便是核心了
        var [x,y ] =  queue.pop();
        console.log(x,y)
        console.log(arr[x][y])
        // 循环四个方向上下左右,将与其值相等的坐标存入数组,并标记,
        // 此处变动一下就是扫了的核心算法了扫雷是周围所有斜着相连的也计算在内
        for(var i = 0;i<direction.length;i++){
            var newx= x+direction[i][0];
            var newy = y+ direction[i][1];
            if(arr[newx][newy]==1&&arrobj[newx][newy]==false){
                queue.push([newx,newy]);
                arrobj[newx][newy] = true
            }
        }
    }
    // 定义结果数组
    var result = [];
    // 循环遍历从存储对象中将结果取出来
    for(var i=0;i<arrobj.length;i++){
        for(var j=0;j<arrobj[i].length;j++){
            if(arrobj[i][j]==true){
                result.push([i,j])
            }
        }
    }
    return result
    
}
var t =doit([3,4]);
console.log(t)

代码详解见注释。算法的问题任何语言都可以解决,主要是理解算法的核心思想。解题函数中初始化定义了一个存储对象和四个方向的数组,通过参数拿到一个坐标,循环遍历与这个坐标相连的四个方向上坐标,也就是上下左右四个坐标。在这个过程中得到的坐标肯定有重复的,所以就用到了一个存储对象,每次循环一个方向得到满足条件的坐标,就在存储对象上面标记一下,下次重复的话就不去处理。循环完成就得到了所有坐标。

点击原文链接查看更多的解题方法,如果你有好的方法或问题,欢迎留言。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-02-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 nodejs全栈开发 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档