LeetCode practice 533: lonely pixel II

I won't say much about the importance of algorithms. If you want to go to a large factory, you must go through the interview of basic knowledge and business logic + algorithm. So, in order to improve the algorithm ability, this official account will be followed up every day to do an algorithm question, and the topic will be selected from LeetCode.

Today's question is called lonely pixel II. Let's look at the question first:


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.

Given an image composed of black pixels and white pixels and a positive integer N, find the number of black pixels in a row R and a column C that meet the following rules:

  • Both row R and column C contain exactly N black pixels.
  • All black pixels in column C must be in exactly the same row as row R.

The image is represented by a two-dimensional character array composed of 'B' and 'W', which represent black pixels and white pixels respectively.


[['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
 analysis: All bold'B'Are all the pixels we want(All of columns 1 and 3'B').
        0    1    2    3    4    5         Column number 
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']] 
Line number

with R = 0 Line sum C = 1 Column'B'take as an example:
Rule 1, R = 0 Line sum C = 1 Columns happen to have N = 3 Black pixels. 
Rule 2, in C = 1 The black pixels of the column are located in rows 0, 1 and 2 respectively. They are all related to R = 0 The rows are identical.

be careful:
The range of rows and columns of the input two-dimensional array is [1,200]. 

Problem solving


Based on the lonely pixel 1, the second condition is further judged

class Solution {
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        vector<int> rows(picture.size(),0);
        vector<int> cols(picture[0].size(),0);
        //Count the number of B in each row and column
        for(int i=0;i<picture.size();++i){
            for(int j=0;j<picture[0].size();++j){
        int res=0;
        //Traverse again for judgment
        for(int i=0;i<picture.size();++i){
            for(int j=0;j<picture[0].size();++j){
              //The current character is B, and the number of corresponding rows and columns is N, indicating that the first condition is met
                  //First, count the rows corresponding to the column
                    vector<int> tmp;
                    for(int k=0;k<picture.size();++k){
                    //Judge whether each row corresponding to the column is the same, that is, whether the second condition is met
                    int pos=1;
                    //If satisfied, add statistics
        return res;

Well, that's all for today's article. If you feel you have something to gain, please click to read or forward it. Your support is my biggest motivation.

Last tweet:

Leetcode 1-520 question summary, I hope it will be of some help to you!

LeetCode practice 521: Longest special sequence I

LeetCode practice 522: Longest special sequence II

LeetCode practice 523: continuous subarray and

LeetCode practice 524: match the longest word in the dictionary by deleting letters

LeetCode practice 525: continuous array

LeetCode practice 526: beautiful arrangement

LeetCode practice 527: word abbreviations

LeetCode practice 528: random selection by weight

LeetCode practice 529: minesweeping game

LeetCode practice 530: minimum absolute difference of binary search tree

LeetCode practice 531: lonely pixel I

LeetCode practice 532: K-diff number pairs in the array

Added by Chrisww on Thu, 03 Mar 2022 10:41:52 +0200