题目描述：

LeetCode 533. Lonely Pixel II

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:

1. Row R and column C both contain exactly N black pixels.
2. 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:

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

题目大意：

给定一个包含字符'W'（白色）和'B'（黑色）的像素矩阵picture，以及一个整数N。

求所有同行同列恰好有N个'B'像素，并且这N行均相同的像素个数。

注意：

二维数组的宽度和高度在范围[1,500]之间。

解题思路：

利用数组rows，cols分别记录某行、某列'B'像素的个数。

然后利用字典sdict统计每一行像素出现的个数。

最后遍历一次picture即可。

Python代码：

class Solution(object):
    def findBlackPixel(self, picture, N):
        """
        :type picture: List[List[str]]
        :type N: int
        :rtype: int
        """
        w, h = len(picture), len(picture[0])
        rows, cols = [0] * w, [0] * h
        for x in range(w):
            for y in range(h):
                if picture[x][y] == 'B':
                    rows[x] += 1
                    cols[y] += 1

        sdict = collections.defaultdict(int)
        for idx, row in enumerate(picture):
            sdict[''.join(row)] += 1

        ans = 0
        for x in range(w):
            row = ''.join(picture[x])
            if sdict[row] != N:
                continue
            for y in range(h):
                if picture[x][y] == 'B':
                    if rows[x] == N:
                        if cols[y] == N:
                            ans += 1
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/03/05/leetcode-lonely-pixel-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码