Description#
Given an m x n picture consisting of black 'B' and white 'W' pixels and an integer target, return the number of black lonely pixels.
A black lonely pixel is a character 'B' that located at a specific position (r, c) where:
- Row
r and column c both contain exactly target black pixels. - For all rows that have a black pixel at column
c, they should be exactly the same as row r.
Example 1:
Input: picture = [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]], target = 3
Output: 6
Explanation: All the green 'B' are the black pixels we need (all 'B's at column 1 and 3).
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 target = 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.
Example 2:
Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1
Output: 0
Constraints:
m == picture.lengthn == picture[i].length1 <= m, n <= 200picture[i][j] is 'W' or 'B'.1 <= target <= min(m, n)
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def findBlackPixel(self, picture: List[List[str]], target: int) -> int:
m, n = len(picture), len(picture[0])
rows = [0] * m
cols = defaultdict(list)
for i in range(m):
for j in range(n):
if picture[i][j] == 'B':
rows[i] += 1
cols[j].append(i)
t = [[False] * m for _ in range(m)]
for i in range(m):
for k in range(i, m):
if i == k:
t[i][k] = True
else:
t[i][k] = all([picture[i][j] == picture[k][j] for j in range(n)])
t[k][i] = t[i][k]
res = 0
for i in range(m):
if rows[i] == target:
for j in range(n):
if len(cols[j]) == target and all([t[i][k] for k in cols[j]]):
res += 1
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public int findBlackPixel(char[][] picture, int target) {
int m = picture.length, n = picture[0].length;
int[] rows = new int[m];
Map<Integer, List<Integer>> cols = new HashMap<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (picture[i][j] == 'B') {
++rows[i];
cols.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
}
}
}
boolean[][] t = new boolean[m][m];
for (int i = 0; i < m; ++i) {
for (int k = i; k < m; ++k) {
t[i][k] = i == k || all(picture[i], picture[k]);
t[k][i] = t[i][k];
}
}
int res = 0;
for (int i = 0; i < m; ++i) {
if (rows[i] == target) {
for (int j = 0; j < n; ++j) {
List<Integer> col = cols.get(j);
if (col != null && col.size() == target) {
boolean check = true;
for (int k : col) {
check = check && t[i][k];
}
if (check) {
++res;
}
}
}
}
}
return res;
}
private boolean all(char[] row1, char[] row2) {
int n = row1.length;
for (int j = 0; j < n; ++j) {
if (row1[j] != row2[j]) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public:
int findBlackPixel(vector<vector<char>>& picture, int target) {
int m = picture.size(), n = picture[0].size();
vector<int> rows(m);
unordered_map<int, vector<int>> cols;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (picture[i][j] == 'B') {
++rows[i];
cols[j].push_back(i);
}
}
}
vector<vector<bool>> t(m, vector<bool>(m, false));
for (int i = 0; i < m; ++i) {
for (int k = i; k < m; ++k) {
t[i][k] = i == k || all(picture[i], picture[k]);
t[k][i] = t[i][k];
}
}
int res = 0;
for (int i = 0; i < m; ++i) {
if (rows[i] == target) {
for (int j = 0; j < n; ++j) {
if (cols[j].size() == target) {
bool check = true;
for (int k : cols[j]) check = check && t[i][k];
if (check) ++res;
}
}
}
}
return res;
}
bool all(vector<char>& row1, vector<char>& row2) {
int n = row1.size();
for (int j = 0; j < n; ++j)
if (row1[j] != row2[j]) return false;
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| func findBlackPixel(picture [][]byte, target int) int {
m, n := len(picture), len(picture[0])
rows := make([]int, m)
cols := make(map[int][]int)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if picture[i][j] == 'B' {
rows[i]++
cols[j] = append(cols[j], i)
}
}
}
t := make([][]bool, m)
for i := 0; i < m; i++ {
t[i] = make([]bool, m)
}
for i := 0; i < m; i++ {
for k := i; k < m; k++ {
if i == k {
t[i][k] = true
} else {
t[i][k] = all(picture[i], picture[k])
}
t[k][i] = t[i][k]
}
}
res := 0
for i := 0; i < m; i++ {
if rows[i] == target {
for j := 0; j < n; j++ {
col, ok := cols[j]
if ok && len(col) == target {
check := true
for _, k := range col {
check = check && t[i][k]
}
if check {
res++
}
}
}
}
}
return res
}
func all(row1, row2 []byte) bool {
n := len(row1)
for i := 0; i < n; i++ {
if row1[i] != row2[i] {
return false
}
}
return true
}
|
