专栏首页chenjx85的技术专栏leetcode-661-Image Smoother

leetcode-661-Image Smoother

题目描述:

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:

  1. The value in the given matrix is in the range of [0, 255].
  2. The length and width of the given matrix are in the range of [1, 150].

要完成的函数:

vector<vector<int>> imageSmoother(vector<vector<int>>& M) 

说明:

1、给定一个二维vector,将其看做是一张图像,对这张图像做平均滤波,也就是每个像素点的值等于(本身的值+周围8个像素点的值)/9。

如果周围没有8个像素,那么尽可能多地采集像素点,比如四个边角,每个边角有4个可计算的点,比如4条边上非边角的像素点,每个点有6个可计算的点。

返回平均滤波得到的二维矩阵,如果除法得到的是小数,那么向下取整。

2、这道题很容易,暴力解法就可以解决。

笔者最开始想要精细化处理,写的代码复杂一些,但是可以降低时间复杂度。

后来觉得实在太麻烦了,不如暴力解法就好,参考了评论区的想法,自己实现了一遍代码,如下:(附详解)

    int avg(int i,int j,vector<vector<int>>&M)//这里一定要加上&,不加重新复制了一遍M,慢了很多
    {
        int sum=0,count=0;
        for(int x=-1;x<=1;x++)
        {
            if(i+x>=0&&i+x<M.size())//前一个条件针对于第一行,后一个条件针对于最后一行
            {
                for(int y=-1;y<=1;y++)
                {
                    if(j+y>=0&&j+y<M[0].size())//前一个条件针对于第一列,后一个条件针对于最后一列
                    {
                        sum+=M[i+x][j+y];
                        count++;
                    }
                }
            }
        }
        return (sum/count);
    }
    
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) 
    {
        int hang=M.size(),lie=M[0].size(),result;
        vector<int>res1(lie,0);
        vector<vector<int>>res(hang,res1);//定义一个和M同样行数同样列数的矩阵res
        for(int i=0;i<hang;i++)
        {
            for(int j=0;j<lie;j++)
                res[i][j]=avg(i,j,M);//对res中的每个值进行处理
        }
        return res;
    }

上述代码中唯一要注意的点就是avg函数的参数矩阵,要加上&,不然会重新复制一份矩阵M,慢了很多。

上述代码实测176ms,beats 85.93% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-566-Reshape the Matrix

    chenjx85
  • leetcode-448-Find All Numbers Disappeared in an Array

    chenjx85
  • leetcode-643-Maximum Average Subarray I

    chenjx85
  • Enum扩展特性,代替中文属性

    把原文中的out参数替换成返回元组,由于项目是vs2015开发,不能用c#7.0特性,否则用7.0中的值元组应该更好一点。性能和显示友好性都会有改进。

    用户6362579
  • 47. 全排列 II【回溯算法】

    输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

    韩旭051
  • Leetcode 78 Subsets

    Given a set of distinct integers, nums, return all possible subsets. Note: The...

    triplebee
  • 海战(线段树)- HDU 4027

    这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

    ACM算法日常
  • 迭代器模式

    迭代器模式(Iterator): 提供一种方法顺序访问一个聚合对象中的各个元素,而又不暴露其内部的表示。 用途:在软件构建过程中,集合对象内部结构常常变化各异。...

    xiangzhihong
  • POJ 2001 Shortest Prefixes

    Description A prefix of a string is a substring starting at the beginning of th...

    attack
  • 六十六、Leetcode数组系列(中篇)

    作者介绍:Runsen目前大三下学期,专业化学工程与工艺,大学沉迷日语,Python, Java和一系列数据分析软件。导致翘课严重,专业排名中下。.在大学60%...

    润森

扫码关注云+社区

领取腾讯云代金券