Skip to content

Latest commit

 

History

History
142 lines (85 loc) · 3.58 KB

0533._Lonely_Pixel_II.md

File metadata and controls

142 lines (85 loc) · 3.58 KB

533. Lonely Pixel II

难度: Medium

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(m^2 * n)- 空间复杂度: O(max(m, n))******

写了一堆发现rule2那么恶心，找了个巧妙的方法, beats 20.00%

class Solution(object):
    def findBlackPixel(self, picture, N):
        """
        :type picture: List[List[str]]
        :type N: int
        :rtype: int
        """
        row = [r.count('B') for r in picture]
        col = [c.count('B') for c in zip(*picture)]
        
        res = 0
        for i in range(len(picture)):
            for j in range(len(picture[0])):
                if picture[i][j] != 'B':
                    continue
                rule1 = row[i] == N and col[j] == N
                if rule1:
                    rule2 = all(picture[k] == picture[i] for k in range(len(picture)) if picture[k][j] == 'B')
                    if rule2:
                        res += 1
                        
        return res

思路 2 - 时间复杂度: O(m * n)- 空间复杂度: O(max(m, n))******

参考Short Python solution that beats 100%

The key insight is that if a valid column (satisfying rule2 and rule1) would contribute exactly N nodes. The problem then reduces to finding the number of valid columns.

The conditions for a valid column are:

  • col.count('B') == N <---- rule 1
  • first_row_with_B_intersecting_with_col.count('B') == N <---- rule 1
  • picture.count(first_row_with_B_intersecting_with_col) == N <---- rule 2

beats 100%

class Solution(object):
    def findBlackPixel(self, picture, N):
        """
        :type picture: List[List[str]]
        :type N: int
        :rtype: int
        """
        valid_col_cnt = 0
        for c in zip(*picture):
            if c.count('B') != N: continue
            first_row = picture[c.index('B')]
            if first_row.count('B') != N: continue
            if picture.count(first_row) != N: continue
            valid_col_cnt += 1
        return valid_col_cnt * N