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:
https://leetcode-cn.com/problems/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: 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.
Example
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
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
https://blog.csdn.net/weixin_44171872/article/details/108937629
Based on the lonely pixel 1, the second condition is further judged
class Solution {
public:
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){
if(picture[i][j]=='B'){
++rows[i];
++cols[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
if(picture[i][j]=='B'&&rows[i]==N&&cols[j]==N){
//First, count the rows corresponding to the column
vector<int> tmp;
for(int k=0;k<picture.size();++k){
if(picture[k][j]=='B'){
tmp.push_back(k);
}
}
//Judge whether each row corresponding to the column is the same, that is, whether the second condition is met
int pos=1;
while(pos<tmp.size()){
if(picture[tmp[0]]!=picture[tmp[pos]]){
break;
}
++pos;
}
//If satisfied, add statistics
if(pos==tmp.size()){
++res;
}
}
}
}
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