资讯专栏INFORMATION COLUMN

前端面试的一道算法题(使用canvas解答)

hot_pot_Leo / 3095人阅读

摘要:据了解,现在前端面试也喜欢考算法题了。下面说一个跟前端有点相关并且有点趣的一道算法题。遍历二维数组连续的个数连续的个数形状的总数第几个形状形状的面积最后的代码图片路径读取整张图片的像素。

据了解,现在前端面试也喜欢考算法题了。前几天去面试,果不其然的,面试官给我四道算法题,让我自己回去做。下面说一个跟前端有点相关并且有点趣的一道算法题。

题目:

平面上有若干个不特定的形状,如下图所示。请写程序求出物体的个数,以及每个不同物体的面积。

分析

想要知道有多少个图形,想到的就是先获取图片中的每一个像素点然后判获取像素点的背景颜色(RGBA)。想要获得图片中的每一个像素点,那就可以联想到使用h5的canvas。
如下:

菜鸟教程中canvas的getimagedata方法

书写html标签。

 对不你,你的浏览器不支持Canvas 

js获取canvas对象

let ctxt = canvas.getContext("2d");

js创建image对象

let img = new Image;
img.src = "./image.png"; //图片路径
img.onload = function(){}  //加载成功后的执行函数,之后的代码就写在其中

创建存储图片像素点的二维数组

let coordinates = [];
for(let i=0; i<200; i++){
       coordinates[i] = [];
}

获取像素点,也就是使用getimagedata方法。

ctxt.drawImage(img, 0, 0);  //将图片画如canvas
let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。

将像素存入二维数组

let x=0,y=0;  //二维数组的行和列, x:列  y:行
for(let i =0,len = data.length; i= 350){
            x = 0;
            y++;
        }
}

目前代码如下:

(function(){
        let ctxt = canvas.getContext("2d");
        let img = new Image;
        let coordinates = [];
        let h = 200,
            w = 350;
        for(let i=0; i<200; i++){
            coordinates[i] = [];
        }
        img.src = "./image.png"; //图片路径
        img.onload = function(){
            ctxt.drawImage(img, 0, 0);
            let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。
            let x=0,y=0;
            for(let i =0,len = data.length; i= 350){
                        x = 0;
                        y++;
                    }
                }
                console.log(coordinates);
        }
    })();

如图:

构成类似如下二维数组:

 0,0,0,0,0,0,0,0,0,0,0,0
 0,0,1,1,1,0,0,0,0,0,0,0
 0,1,1,1,1,0,0,0,0,0,0,0
 0,1,1,1,0,0,0,1,1,1,1,0
 0,0,0,0,0,0,1,1,1,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

那么我们就只需要知道二维数组中这种连续为1的块有多少个就知道了图片中形状有多少个,并且块中有多少个1,那么这个块的面积就是1的个数。

递归回溯算法
//计算连续的面积和个数
const linkSum = (i,j,num)=>{
        //走过的路就置0
      coordinates[i][j] = 0;
      num++;
      //向上
      if((i+1 < h) && coordinates[i+1][j] == 1){
        num = linkSum(i+1 , j , num);
      }
      //向下
      if((j+1 < w) && coordinates[i][j+1] == 1){
        num = linkSum(i , j+1 , num);
      }
      //向左
      if((i-1 >= 0) && coordinates[i-1][j] == 1){
        num = linkSum(i-1 , j , num);
      }
      //向右
    if((j-1 >= 0) && coordinates[i][j-1] == 1){
        num = linkSum(i , j-1 , num);
    }

    return num;
}

不熟悉的,直接百度就好,这里就不多说了,其实代码就反应了很多信息。

使用算法,统计并计算出结果。
const getCountAndArea = () =>{
    let sum = [];
    let count = 0;
    for(let i = 0; i < h; i++)  //遍历二维数组
    {
      for(let j = 0; j < w; j++)
      {
       //连续1的个数
       if(coordinates[i][j] == 1)
       {
        let buf = 0;  //连续1的个数
        buf = linkSum(i,j,buf);
        count++;  //形状的总数
        sum.push({
            index: count,   //第几个形状
            area: buf         //形状的面积
        });
       }
      }
    }
    return {
        count,
        sum
    };
}
最后的代码
(function(){
        let ctxt = canvas.getContext("2d");
        let img = new Image;
        let coordinates = [];
        let h = 200,
            w = 350;
        for(let i=0; i<200; i++){
            coordinates[i] = [];
        }
        img.src = "./image.png"; //图片路径
        img.onload = function(){
            ctxt.drawImage(img, 0, 0);
            let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。
            let x=0,y=0;
            for(let i =0,len = data.length; i= 350){
                        x = 0;
                        y++;
                    }
                }
                // console.log(coordinates);
                let rst = getCountAndArea();
                // console.log(rst);
                console.log("个数: " + rst.count);
                for(let i=0; i{
            let sum = [];
            let count = 0;
            for(let i = 0; i < h; i++)
            {
              for(let j = 0; j < w; j++)
              {
               //连续1的个数
               if(coordinates[i][j] == 1)
               {
                let buf = 0;
                buf = linkSum(i,j,buf);
                count++;
                sum.push({
                    index: count,
                    area: buf
                });
               }
              }
            }
            return {
                count,
                sum
            };
        }

        //计算连续的面积和个数
        const linkSum = (i,j,num)=>{
            //走过的路就置0
          coordinates[i][j] = 0;
          num++;
          //向上
          if((i+1 < h) && coordinates[i+1][j] == 1){
            num = linkSum(i+1 , j , num);
          }
          //向下
          if((j+1 < w) && coordinates[i][j+1] == 1){
            num = linkSum(i , j+1 , num);
          }
          //向左
          if((i-1 >= 0) && coordinates[i-1][j] == 1){
            num = linkSum(i-1 , j , num);
          }
          //向右
        if((j-1 >= 0) && coordinates[i][j-1] == 1){
            num = linkSum(i , j-1 , num);
        }

        return num;
        }
    })();
运行的结果:

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/87030.html

相关文章

  • 深入理解js

    摘要:详解十大常用设计模式力荐深度好文深入理解大设计模式收集各种疑难杂症的问题集锦关于,工作和学习过程中遇到过许多问题,也解答过许多别人的问题。介绍了的内存管理。 延迟加载 (Lazyload) 三种实现方式 延迟加载也称为惰性加载,即在长网页中延迟加载图像。用户滚动到它们之前,视口外的图像不会加载。本文详细介绍了三种延迟加载的实现方式。 详解 Javascript十大常用设计模式 力荐~ ...

    caikeal 评论0 收藏0
  • canvas getImageData 做点有趣

    摘要:回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。代码请点这里这里有一个示例,展示下用回溯法怎么找到这些形状的。 说明 canvas元素标签强大之处在于可以直接在HTML上进行图形操作,具有极大的应用价值。 canvas 可以实现对图像的像素操作,这就要说到 getImag...

    chenatu 评论0 收藏0
  • 2017 前端面试准备 - 收藏集 - 掘金

    摘要:最近遇到的前端面试题更新版前端掘金个人博客已上线,欢迎前去访问评论无媛无故的个人博客以下内容非本人原创,是整理后觉得更容易理解的版本,欢迎补充。 一道面试题引发的对 javascript 类型转换的思考 - 前端 - 掘金 最近群里有人发了下面这题:实现一个函数,运算结果可以满足如下预期结果: ... 收集 JavaScript 各种疑难杂症的问题集锦 - 前端 - 掘金 从原博客迁移...

    王晗 评论0 收藏0
  • 2017 前端面试准备 - 收藏集 - 掘金

    摘要:最近遇到的前端面试题更新版前端掘金个人博客已上线,欢迎前去访问评论无媛无故的个人博客以下内容非本人原创,是整理后觉得更容易理解的版本,欢迎补充。 一道面试题引发的对 javascript 类型转换的思考 - 前端 - 掘金 最近群里有人发了下面这题:实现一个函数,运算结果可以满足如下预期结果: ... 收集 JavaScript 各种疑难杂症的问题集锦 - 前端 - 掘金 从原博客迁移...

    xiaochao 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<