难度: Medium
Submission
运行时间: 56 ms
内存: 20.5 MB
class Solution:
def findBlackPixel(self, picture: List[List[str]], N: int) -> int:
#状态压缩
R, C = len(picture), len(picture[0])
row_mode_freq = defaultdict(int)
row_mode_cnt = defaultdict(int)
col_cnt = defaultdict(int)
for row in picture:
row_mode = ''.join(row)
row_mode_freq[row_mode] += 1
if row_mode not in row_mode_cnt:
cnt = 0
for c in range(C):
if row[c] == 'B':
cnt += 1
row_mode_cnt[row_mode] = cnt
print(row_mode_cnt)
print(row_mode_freq)
for r in range(R):
for c in range(C):
if picture[r][c] == 'B':
col_cnt[c] += 1
print(col_cnt)
res = 0
for row_mode, freq in row_mode_freq.items():
if freq == N: #小于N，就实现不了 若大于N，则一个B点所在的列，必然超过了N个B
for c in range(C):
if row_mode[c] == 'B' and row_mode_cnt[row_mode] == N and col_cnt[c] == N:
res += N
return res
Explain
这个题解使用了状态压缩的思路。首先统计每一行的模式（即每一行的像素组成的字符串）出现的频率，以及每种模式中黑色像素的数量。然后统计每一列中黑色像素的数量。最后遍历所有的行模式，如果某个行模式出现的频率等于N，并且该模式中黑色像素的数量也等于N，同时每个黑色像素所在的列中黑色像素的数量也等于N，那么就找到了符合条件的黑色像素，将其数量累加到结果中。
时间复杂度: O(RC)
空间复杂度: O(R+C)
class Solution:
def findBlackPixel(self, picture: List[List[str]], N: int) -> int:
# 状态压缩
R, C = len(picture), len(picture[0])
row_mode_freq = defaultdict(int) # 存储每种行模式出现的频率
row_mode_cnt = defaultdict(int) # 存储每种行模式中黑色像素的数量
col_cnt = defaultdict(int) # 存储每一列中黑色像素的数量
# 统计每一行的模式和黑色像素数量
for row in picture:
row_mode = ''.join(row)
row_mode_freq[row_mode] += 1
if row_mode not in row_mode_cnt:
cnt = 0
for c in range(C):
if row[c] == 'B':
cnt += 1
row_mode_cnt[row_mode] = cnt
# 统计每一列中黑色像素的数量
for r in range(R):
for c in range(C):
if picture[r][c] == 'B':
col_cnt[c] += 1
res = 0
# 遍历所有的行模式
for row_mode, freq in row_mode_freq.items():
if freq == N: # 行模式出现的频率等于N
for c in range(C):
# 判断黑色像素是否满足条件
if row_mode[c] == 'B' and row_mode_cnt[row_mode] == N and col_cnt[c] == N:
res += N
return res
Explore
在题解中，判断一个行模式是否符合条件需要满足以下三个条件：1) 该行模式出现的频率必须等于N，确保这种模式的行恰好出现了N次；2) 该行模式中黑色像素的数量也必须等于N，确保每一行都恰有N个黑色像素；3) 对于行模式中每一个黑色像素所在的列，这一列中黑色像素的总数量也必须等于N，确保每一个黑色像素在其所在列中唯一且该列黑色像素数量正好为N。只有当这三个条件同时满足时，该行模式中的黑色像素才符合题目的要求。
在统计每一列黑色像素数量时选择使用哈希表（如defaultdict）而不是数组可能是出于代码的通用性和可读性考虑。尽管列数C是固定的，使用数组确实可以做到更高效的空间和时间性能。但在某些情况下，使用哈希表可以更灵活地处理不同的情况，例如处理列数很大或者动态变化的场景。此外，使用defaultdict可以自动处理不存在的键的情况，简化代码实现。
题解中最后部分的逻辑中，对于每个符合条件的黑色像素，结果累加的是N而不是1，这是因为题解的逻辑中已经通过行模式的频率检查确保了每种符合条件的行模式恰好出现N次。因此，当找到一个黑色像素符合所有条件时，实际上已经确定了这种特定行模式中的每个黑色像素（共N个）都分别出现在N个不同的行中，每行一个。因此，直接将结果累加N，是为了统计所有这些行中的黑色像素。
题解中使用defaultdict主要是因为它提供了自动化的默认值处理。在普通字典中，如果尝试访问一个不存在的键，会抛出一个KeyError。而在defaultdict中，如果访问的键不存在，它会自动创建这个键并将其值设置为指定的默认类型的初始值（例如int的0，list的空列表等）。这在统计过程中非常有用，可以减少代码中的错误检查和键存在性验证，使代码更简洁、易读和易于维护。