Weekly contest 46

Image Smoother

My SubmissionsBack to Contest

• User Accepted:1292
• User Tried:1414
• Total Accepted:1306
• Total Submissions:2523
• Difficulty:Easy

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].

class Solution {
public:
    int n_sum(vector<vector<int>>& M, int i, int j, int& total) {
        int i_end = M.size(), j_end = M[0].size();
        if (i < 0 || i >= i_end || j < 0 || j >= j_end) {
            return 0;
        }
        total++;
        return M[i][j];
    }

    double avg(vector<vector<int>>& M, int i, int j) {
        int sum = M[i][j], total = 1;
        sum += n_sum(M, i - 1, j - 1, total);
        sum += n_sum(M, i - 1, j, total);
        sum += n_sum(M, i - 1, j + 1, total);
        sum += n_sum(M, i, j - 1, total);
        sum += n_sum(M, i, j + 1, total);
        sum += n_sum(M, i + 1, j - 1, total);
        sum += n_sum(M, i + 1, j, total);
        sum += n_sum(M, i + 1, j + 1, total);
        
        return sum/total;
    }
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        vector<vector<int>> ans(M);
        for (int i = 0; i < M.size(); i++) {
            for (int j = 0; j < M[i].size(); j++) {
                ans[i][j] = avg(M, i, j);
            }
        }
        return ans;
    }
};

================

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note: Answer will in the range of 32-bit signed integer.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void process(vector<TreeNode *>& q) {
        int size = q.size();
        int st = 0, end = size - 1;
        while (q[st] == NULL && st <= end) {
            st++;
        }
     
        while (st < end && q[end] == NULL) {
            end--;
        }
     
        if (st != 0) {
            q.erase(q.begin(), q.begin() + st);
        }
        if (end != size - 1) {
            q.erase(q.begin() + end - st + 1, q.end());
        }
        return;  
    }

    int widthOfBinaryTree(TreeNode* root) {
        int ans = 0;
        if (root == NULL) {
            return ans;
        }
        ans = 1;
        vector<TreeNode *> q, child_q;
        q.push_back(root);
        while (!q.empty()) {
            for (int j = 0; j < q.size(); j++) {
                if (q[j] == NULL) {
                    child_q.push_back(NULL);
                    child_q.push_back(NULL);
                } else {
                    child_q.push_back(q[j] -> left);
                    child_q.push_back(q[j] -> right);
                }
            }
            process(child_q);
            int child_len = child_q.size();
            ans = max(ans, child_len);
            q = child_q;
            child_q.clear();
        }
        return ans;
    }
};