数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中的孤独像素 II
假设我们有一张由黑白像素组成的图片，我们需要找到在第 R 行和第 C 列中存在的黑色像素的数量。该数量必须符合以下所有规则：
R 和 C 将恰好包含 N 个黑色像素。
对于所有在第 C 列具有黑色像素的行，它们都应该与第 R 行完全相同。
这里图片由一个二维字符数组表示，其中 'B' 和 'W' 分别代表黑色和白色像素。
如果输入如下：
| 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，则输出将为 6。因为所有加粗的 'B' 都是黑色像素，所有位于第 1 列和第 3 列的 'B'。现在，如果我们取第 R = 0 行和第 C = 1 列的 'B' 作为示例：规则 1，第 R = 0 行和第 C = 1 列都恰好有 N 个 'B' 像素。并且规则 2，在第 C = 1 列具有 'B' 像素的行是第 0 行、第 1 行和第 2 行。它们与第 R = 0 行完全相同。
为了解决这个问题，我们将遵循以下步骤：
ret := 0
定义一个映射 r 和另一个映射 c
n := p 的行数，m := p 的列数
初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
如果 p[i, j] 等于 'B'，则：
将 j 插入到 r[i] 中
将 i 插入到 c[j] 中
初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
初始化 j := 0，当 j < m 且 i 在 r 中时，更新（j 加 1），执行：
如果 p[i, j] 等于 'B' 且 r[i] 的大小等于 N 且 c[j] 的大小等于 N，则：
ok := true
对于 c[j] 中的每个 x，执行
如果 r[x] 不等于 r[i]，则：
ok := false
退出循环
ret := ret + ok
返回 ret
示例（C++）
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findBlackPixel(vector<vector<char>>& p, int N) {
int ret = 0;
unordered_map <int, set <int> > r, c;
int n = p.size();
int m = p[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(p[i][j] == 'B'){
r[i].insert(j);
c[j].insert(i);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m && r.count(i); j++){
if(p[i][j] == 'B' && r[i].size() == N && c[j].size() == N){
bool ok = true;
for(auto& x : c[j]){
if(r[x] != r[i]){
ok = false;
break;
}
}
ret += ok;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<char>> v = {{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B' ,'B','W'},{'W','W','B','W','B','W'}};
cout << (ob.findBlackPixel(v, 3));
}输入
{{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B' ,'B','W'},{'W','W','B','W','B','W'}}, 3输出
6
82 次查看
