砖墙
难度:
标签:
题目描述
你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。
你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
示例 1：
输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] 输出：2
示例 2：
输入：wall = [[1],[1],[1]] 输出：3
提示：
n == wall.length1 <= n <= 1041 <= wall[i].length <= 1041 <= sum(wall[i].length) <= 2 * 104- 对于每一行
i，sum(wall[i])是相同的 1 <= wall[i][j] <= 231 - 1
代码结果
运行时间: 35 ms, 内存: 19.7 MB
// 思路：
// 与上面的方法类似，只是我们利用Java Stream来实现
// 使用Collectors.groupingBy来统计间隙出现的次数，然后找出最大值，最后计算结果
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class Solution {
public int leastBricks(List<List<Integer>> wall) {
Map<Integer, Long> gapCount = wall.stream()
.flatMap(row -> {
int sum = 0;
return row.stream().limit(row.size() - 1).map(width -> {
sum += width;
return sum;
});
})
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
long maxGap = gapCount.values().stream().max(Long::compare).orElse(0L);
return (int) (wall.size() - maxGap);
}
}解释
方法:
此题解采用了哈希表来记录砖墙中每一行砖块的边缘位置出现的次数。首先，遍历砖墙的每一行，计算每一块砖的右边缘位置，并将这个位置作为键，其出现的次数作为值存储到哈希表中。需要注意的是，最后一块砖的右边缘不计入哈希表，因为按照题目要求，不能沿着墙的两个垂直边缘之一画线。在遍历的过程中，还需要记录下出现次数最多的边缘位置的次数。最后，用墙的总行数减去这个最大次数，就得到了穿过的砖块数量最少的情况。
时间复杂度:
O(n*m)
空间复杂度:
O(k)
代码细节讲解
🦆
为什么在计算砖块边缘位置时，不包括每行最后一块砖的右边缘？
▷🦆
哈希表中记录的键是砖块的右边缘位置，那么这个位置是相对于墙的左边缘还是相对于上一块砖的右边缘？
▷🦆
在确定哈希表中出现次数最多的边缘位置时，如果有多个位置出现次数相同怎么处理？
▷🦆
代码中`seap`字典的命名是基于什么考虑？是否有更具描述性的替代名称？
▷