leetcode
leetcode 451 ~ 500
孤独像素 II

孤独像素 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)

代码细节讲解

🦆
在题解中,你是如何判断一个行模式是否符合条件的?具体是哪些条件需要同时满足?
在题解中,判断一个行模式是否符合条件需要满足以下三个条件:1) 该行模式出现的频率必须等于N,确保这种模式的行恰好出现了N次;2) 该行模式中黑色像素的数量也必须等于N,确保每一行都恰有N个黑色像素;3) 对于行模式中每一个黑色像素所在的列,这一列中黑色像素的总数量也必须等于N,确保每一个黑色像素在其所在列中唯一且该列黑色像素数量正好为N。只有当这三个条件同时满足时,该行模式中的黑色像素才符合题目的要求。
🦆
在统计每一列黑色像素数量时,为何选择使用哈希表而不是数组,尽管列数C是固定的?
在统计每一列黑色像素数量时选择使用哈希表(如defaultdict)而不是数组可能是出于代码的通用性和可读性考虑。尽管列数C是固定的,使用数组确实可以做到更高效的空间和时间性能。但在某些情况下,使用哈希表可以更灵活地处理不同的情况,例如处理列数很大或者动态变化的场景。此外,使用defaultdict可以自动处理不存在的键的情况,简化代码实现。
🦆
题解中最后部分的逻辑,对于每个符合条件的黑色像素,为何结果累加的是N而不是1?
题解中最后部分的逻辑中,对于每个符合条件的黑色像素,结果累加的是N而不是1,这是因为题解的逻辑中已经通过行模式的频率检查确保了每种符合条件的行模式恰好出现N次。因此,当找到一个黑色像素符合所有条件时,实际上已经确定了这种特定行模式中的每个黑色像素(共N个)都分别出现在N个不同的行中,每行一个。因此,直接将结果累加N,是为了统计所有这些行中的黑色像素。
🦆
题解使用了defaultdict进行数据存储,这种结构在此题中相比普通字典有什么优势?
题解中使用defaultdict主要是因为它提供了自动化的默认值处理。在普通字典中,如果尝试访问一个不存在的键,会抛出一个KeyError。而在defaultdict中,如果访问的键不存在,它会自动创建这个键并将其值设置为指定的默认类型的初始值(例如int的0,list的空列表等)。这在统计过程中非常有用,可以减少代码中的错误检查和键存在性验证,使代码更简洁、易读和易于维护。

相关问题

孤独像素 I

孤独像素 I