数据结构与算法-砖墙问题

砖墙问题

你的面前有一堵矩形的、由 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())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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