题目
难度：★★★☆☆
类型：数组
方法：哈希
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
示例：
输入: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
输出: 2
解答
还记得微信小程序欢乐球球吗？也是希望你可以穿过的缝隙尽可能多，而尽可能少的撞到砖头。
欢乐球球
我们使用哈希表来解决这个问题。我们观察到的一层层的砖头和缝隙。我们希望构建这样一个哈西表，这个表中所有表示整个墙上所有缝隙的横坐标，纵坐标表示该位置所在直线穿过的缝隙的数目，通过逐层的遍历就可以获得这个哈希表。最后，我们要使用的是这个哈希表中缝隙数目最大的情况。
class Solution:
def leastBricks(self, wall):
loc_gaps = {}
for layer in wall:
sums = 0
for index in range(len(layer)-1): # 这里-1是因为整个墙的最右端竖线是不能考虑的
sums += layer[index]
loc_gaps[sums] = loc_gaps.get(sums, 0) + 1 # get意思是如果有值，取该值，如果没有，返回0
if len(loc_gaps) == 0:
return len(wall)
return len(wall) - max(loc_gaps.values()) # 总层数减去裂缝数就是砖头的数目
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
