砖墙问题

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

问题假设：墙的宽度与每层砖的宽度一致，则之寻找砖缝

class Solution(object):def leastBricks(self,wall):""":type wall: List[List[int]]:rtype: int"""# 用来存储缝的数组，最大的缝的个数等于每行砖块的宽度f = Counter()levels = len(wall)# 当每行的缝全为1时，则没有最大为len(wall)# 遍历每一行for line in wall:# 遍历第一行中的砖块，查找砖缝# temp用于计算累加砖块宽度temp= 0for i in line:temp += i# 当计算到边缘砖块时跳出循环if temp == sum(wall[0]):breakf[temp-1]+=1# 只存在一种宽度的砖块情况if not f:return levels else:return levels - max(f.values())

采用数组记录砖缝，容易导致内存溢出，因此采用哈希表进行记录