Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is 661 on LeetCode. Image smoothing, easy to do.

Tag: “simulation”, “prefix and”

Image smoothing is a filter with a size of 3∗33 * 33∗3, which is used to smooth each cell of the image, and the value of the cell after smoothing is the average gray level of the cell.

The average gray scale of each cell is defined as: the average value of the cell itself and its 888 surrounding cells, and the result needs to be rounded down. (That is, you need to calculate the average of 999 cells in the blue smoother).

If there are missing cells around a cell, the missing cells are not considered when calculating the average gray level (that is, the average of the 444 cells in the red smoother needs to be calculated).

You are given a M ∗nm * nm∗ N integer matrix img that represents the grayscale of the image and returns the image smoothed for each cell of the image.

Example 1:

Input: img = [,1,1 [1], [1, 1], [1,1,1]] output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]] : for point (0, 0), (0, 2), (2, 0), (2, 2) : Average (3/4) = average (0.75) = 0 for point (0, 1), (1, 0), (1, 2), (2, 1) : the average (5/6) = average (0.83333333) = 0 for point (1, 1) : Average (8/9) = average (0.88888889) = 0Copy the code

Example 2:

Input: img = [[100200100], [200,50,200], [100200100]] output: [[137141137], [141138141], [137141137]] : For point (0, 0), (0, 2), (2, 0), (2, 2) : floor ((100 + 200 + 200 + 50) / 4) = floor (137.5) = 137 for point (0, 1), (1, 0), (1, 2), (2, 1) : Floor ((200+200+50+200+100+100)/6) = floor(141.666667) = 141 Floor ((50+200+200+200+ 100+100+100+100 +100)/9) = floor(138.888889) = 138Copy the code

Tip:


  • m = = i m g . l e n g t h m == img.length

  • n = = i m g [ i ] . l e n g t h n == img[i].length

  • 1 < = m . n < = 200 1 <= m, n <= 200

  • 0 < = i m g [ i ] [ j ] < = 255 0 <= img[i][j] <= 255

Simple solution

For convenience, we call each cell and its connected block of eight connected directional cells an item.

The data range is only 200200200, so we can directly simulate each item through traversal.

Code:

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] ans = new int[m][n];
        int[][] dirs = new int[] [] {{0.0}, {1.0}, {-1.0}, {0.1}, {0, -1}, {-1, -1}, {-1.1}, {1, -1}, {1.1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int tot = 0, cnt = 0;
                for (int[] di : dirs) {
                    int nx = i + di[0], ny = j + di[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; tot += img[nx][ny]; cnt++; } ans[i][j] = tot / cnt; }}returnans; }}Copy the code


class Solution:
    def imageSmoother(self, img: List[List[int]]) - >List[List[int]] :
        m, n = len(img), len(img[0])
        dirs = [[i, j] for i in range(-1.2) for j in range(-1.2)]
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                tot, cnt = 0.0
                for di in dirs:
                    nx, ny = i + di[0], j + di[1]
                    if nx < 0 or nx >= m or ny < 0 or ny >= n:
                        continue
                    tot += img[nx][ny]
                    cnt += 1
                ans[i][j] = tot // cnt
        return ans
Copy the code
  • Time complexity: O(M ∗n∗C)O(M * N * C)O(M ∗n∗C), where CCC refers to the number of cells contained in a grayscale unit, which is fixed at 999
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

The prefix and

In the naive solution, for every ans[I][j]ans[I][j]ans[I][I]ans[I][j]ans[I][j] we cannot avoid traversing the 888 unicom direction, and we can optimize this operation with “prefix sum”.

For an ans[I][j]ans[I][j]ans[I][j] We can directly calculate its place at the upper left of the item (a, b) = (I – 1, j – 1) (a, b) = (I – 1, j – 1) (a, b) = (I – 1, j – 1) and its lower right corner (c, d) = (I + 1, j + 1) (c, d) = (I + 1, J + 1) (c, d) = (I + 1, j + 1), in order to prevent beyond the original matrix at the same time, we need to put (a, b) (a, b) (a, b) and (c, d) (c, d) (c, d) to the boundary take Max and min, respectively.

After we have the legal (a,b)(a, b)(a,b) and (c,d)(c, d)(c,d) (c,d)(c, d), we can directly calculate the number of cells of item (product of contained rows and columns) and the sum of the cells of item (prefix and query). So we can calculate ans[I][j]ans[I][j].

Code:

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] sum = new int[m + 10][n + 10];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]; }}int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int a = Math.max(0, i - 1), b = Math.max(0, j - 1);
                int c = Math.min(m - 1, i + 1), d = Math.min(n - 1, j + 1);
                int cnt = (c - a + 1) * (d - b + 1);
                int tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]; ans[i][j] = tot / cnt; }}returnans; }}Copy the code


class Solution:
    def imageSmoother(self, img: List[List[int]]) - >List[List[int]] :
        m, n = len(img), len(img[0])
        sum = [[0] * (n + 10) for _ in range(m + 10)]
        for i in range(1, m + 1) :for j in range(1, n + 1) :sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                a, b = max(0, i - 1), max(0, j - 1)
                c, d = min(m - 1, i + 1), min(n - 1, j + 1)
                cnt = (c - a + 1) * (d - b + 1)
                tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]
                ans[i][j] = tot // cnt
        return ans
Copy the code
  • Time complexity: O(m∗n)O(m * n)O(m∗n)
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

Same type of extra meals

Extra meal of the day:【 interview frequency questions 】 Difficulty 1.5/5, a “bucket sort + prefix sum” optimization questions 🎉 🎉

The last

This is the No.661 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.