孤独像素 II
难度:
标签:
题目描述
代码结果
运行时间: 56 ms, 内存: 20.5 MB
/*
* 题目思路:
* 我们需要找到所有黑色像素'B'的列数, 使得满足条件的列数的数量等于N
* 而且每一行只包含恰好N个黑色像素。
*
* 为了实现这一点,我们需要遍历二维字符数组并计数每行和每列中的黑色像素。
* 我们还需要检查这些行是否有相同的黑色像素列。
*
* 使用Java Stream API来实现上述功能。
*/
import java.util.*;
import java.util.stream.*;
public class LonelyPixelIIStream {
public int findBlackPixel(char[][] picture, int N) {
int rows = picture.length;
int cols = picture[0].length;
int[] rowCount = new int[rows];
int[] colCount = new int[cols];
Map<String, Long> rowMap = Arrays.stream(picture)
.map(String::new)
.collect(Collectors.groupingBy(row -> row, Collectors.counting()));
IntStream.range(0, rows).forEach(i -> {
IntStream.range(0, cols).forEach(j -> {
if (picture[i][j] == 'B') {
rowCount[i]++;
colCount[j]++;
}
});
});
return (int) IntStream.range(0, rows).filter(i -> rowCount[i] == N)
.boxed()
.flatMap(i -> IntStream.range(0, cols)
.filter(j -> picture[i][j] == 'B' && colCount[j] == N)
.mapToObj(j -> new AbstractMap.SimpleEntry<>(i, j)))
.filter(entry -> rowMap.get(new String(picture[entry.getKey()])) == N)
.count();
}
}
解释
方法:
这个题解使用了状态压缩的思路。首先统计每一行的模式(即每一行的像素组成的字符串)出现的频率,以及每种模式中黑色像素的数量。然后统计每一列中黑色像素的数量。最后遍历所有的行模式,如果某个行模式出现的频率等于N,并且该模式中黑色像素的数量也等于N,同时每个黑色像素所在的列中黑色像素的数量也等于N,那么就找到了符合条件的黑色像素,将其数量累加到结果中。
时间复杂度:
O(RC)
空间复杂度:
O(R+C)
代码细节讲解
🦆
在题解中,你是如何判断一个行模式是否符合条件的?具体是哪些条件需要同时满足?
▷🦆
在统计每一列黑色像素数量时,为何选择使用哈希表而不是数组,尽管列数C是固定的?
▷🦆
题解中最后部分的逻辑,对于每个符合条件的黑色像素,为何结果累加的是N而不是1?
▷🦆
题解使用了defaultdict进行数据存储,这种结构在此题中相比普通字典有什么优势?
▷