美文网首页
533. Lonely Pixel II

533. Lonely Pixel II

作者: matrxyz | 来源:发表于2018-01-13 17:22 被阅读0次

    Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:
    Row R and column C both contain exactly N black pixels.
    For all rows that have a black pixel at column C, they should be exactly the same as row R
    The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

    Example:
    Input:                                            
    [['W', 'B', 'W', 'B', 'B', 'W'],    
     ['W', 'B', 'W', 'B', 'B', 'W'],    
     ['W', 'B', 'W', 'B', 'B', 'W'],    
     ['W', 'W', 'B', 'W', 'B', 'W']] 
    
    N = 3
    Output: 6
    Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
            0    1    2    3    4    5         column index                                            
    0    [['W', 'B', 'W', 'B', 'B', 'W'],    
    1     ['W', 'B', 'W', 'B', 'B', 'W'],    
    2     ['W', 'B', 'W', 'B', 'B', 'W'],    
    3     ['W', 'W', 'B', 'W', 'B', 'W']]    
    row index
    
    Take 'B' at row R = 0 and column C = 1 as an example:
    Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
    Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.
    

    Note:
    The range of width and height of the input 2D array is [1,200].

    Solution:

    思路:
    给了一个整数N,说对于均含有N个黑像素的某行某列,如果该列中所有的黑像素所在的行都相同的话,该列的所有黑像素均为孤独的像素,让我们统计所有的这样的孤独的像素的个数。

    那么跟之前那题类似,我们还是要统计每一行每一列的黑像素的个数,而且由于条件二中要比较各行之间是否相等,如果一个字符一个字符的比较写起来比较麻烦,我们可以用个trick,把每行的字符连起来,形成一个字符串,然后直接比较两个字符串是否相等会简单很多(用hashmap(string, count))。然后我们遍历每一行和每一列,如果某行和某列的黑像素刚好均为N,我们遍历该列的所有黑像素,如果其所在行均相等,则说明该列的所有黑像素均为孤独的像素,将个数加入结果res中,然后将该行的黑像素统计个数清零,以免重复运算,这样我们就可以求出所有的孤独的像素了,

    Time Complexity: O(N) Space Complexity: O(N)

    Solution Code:

    // 孤独的点要满足:
    // (1) 该行有N个黑点
    // (2) 该列有N个黑点
    // (3) 该列中所有的黑像素所在的行都相同
    public class Solution {
        public int findBlackPixel(char[][] picture, int N) {
            if(picture == null || picture.length == 0 || picture[0].length == 0) return 0;
            int m = picture.length;
            int n = picture[0].length;
            
            Map<String, Integer> map = new HashMap<>();
            int[] colCount = new int[n];
            
            // (预备3)行编码存入map,(预备2)统计列的B,并check(1)该行B的个数是否为N
            for (int i = 0; i < m; i++) {
                String key = scanRow(picture, i, N, colCount);
                if (key.length() != 0) {
                    map.put(key, map.getOrDefault(key, 0) + 1);
                }
            }
            
            // check(3) 及 check(2)该列B的个数是否为N
            int result = 0;
            for (String key : map.keySet()) {
                if (map.get(key) == N) {
                    for (int j = 0; j < n; j++) {
                        if (key.charAt(j) == 'B' && colCount[j] == N) {
                            result += N;
                        }
                    }
                }
            }
            
            return result;
        }
        
        private String scanRow(char[][] picture, int row, int target, int[] colCount) {
            int n = picture[0].length;
            int rowCount = 0;
            StringBuilder sb = new StringBuilder();
            
            for (int j = 0; j < n; j++) {
                if (picture[row][j] == 'B') {
                    rowCount++;
                    colCount[j]++;
                }
                sb.append(picture[row][j]);
            }
            
            if (rowCount == target) return sb.toString();
            return "";
        }
    }
    

    相关文章

      网友评论

          本文标题:533. Lonely Pixel II

          本文链接:https://www.haomeiwen.com/subject/ciicoxtx.html