题目

难度：★★★☆☆
类型：数组
方法：哈希

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。

如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。

你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

示例：

输入: [[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解决方案，请移步力扣中等题解析