砖墙问题
你的面前有一堵矩形的、由 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= 0
for i in line:
temp += i
# 当计算到边缘砖块时跳出循环
if temp == sum(wall[0]):
break
f[temp-1]+=1
# 只存在一种宽度的砖块情况
if not f:
return levels
else:
return levels - max(f.values())
采用数组记录砖缝,容易导致内存溢出,因此采用哈希表进行记录