砖墙

标签: 数组 哈希表

难度: Medium

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

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

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

 

示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：

输入：wall = [[1],[1],[1]]
输出：3
 

提示：

  • n == wall.length
  • 1 <= n <= 104
  • 1 <= wall[i].length <= 104
  • 1 <= sum(wall[i].length) <= 2 * 104
  • 对于每一行 i ，sum(wall[i]) 是相同的
  • 1 <= wall[i][j] <= 231 - 1

Submission

运行时间: 35 ms

内存: 19.7 MB

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        seap = {}
        maxnum = 0
        count = sum(wall[0])
        for level in wall:
            sumnum = 0
            for num in level:
                sumnum += num
                if sumnum != count:
                    if sumnum not in seap.keys():
                        seap[sumnum] = 0
                    seap[sumnum] += 1
                    if seap[sumnum]>maxnum:
                        maxnum = seap[sumnum]
        
        return len(wall) - maxnum

Explain

此题解采用了哈希表来记录砖墙中每一行砖块的边缘位置出现的次数。首先，遍历砖墙的每一行，计算每一块砖的右边缘位置，并将这个位置作为键，其出现的次数作为值存储到哈希表中。需要注意的是，最后一块砖的右边缘不计入哈希表，因为按照题目要求，不能沿着墙的两个垂直边缘之一画线。在遍历的过程中，还需要记录下出现次数最多的边缘位置的次数。最后，用墙的总行数减去这个最大次数，就得到了穿过的砖块数量最少的情况。

时间复杂度: O(n*m)

空间复杂度: O(k)

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        seap = {}
        maxnum = 0
        count = sum(wall[0])
        for level in wall:
            sumnum = 0
            for num in level:
                sumnum += num
                if sumnum != count:
                    if sumnum not in seap.keys():
                        seap[sumnum] = 0
                    seap[sumnum] += 1
                    if seap[sumnum] > maxnum:
                        maxnum = seap[sumnum]
        
        return len(wall) - maxnum

Explore

在计算砖块边缘位置时，不包括每行最后一块砖的右边缘是因为题目要求画的线不能沿着墙的两个垂直边缘之一。如果包括最后一块砖的右边缘，那么这个边缘实际上就是墙的右侧边缘，这样的线是不被允许的。因此，只考虑到最后一块砖之前的边缘位置，以避免画线违反题目的要求。

哈希表中记录的键，即砖块的右边缘位置，是相对于墙的左边缘来计算的。在代码中，通过累加每一行中每块砖的长度来更新`sumnum`变量，这样每次累加后的`sumnum`就代表从墙的左边缘到当前砖块右边缘的总距离。

在确定哈希表中出现次数最多的边缘位置时，如果有多个位置出现次数相同，则这些位置都可以被视为最优的边缘位置，因为它们穿过的砖块数量都是最少的。从算法的角度来看，只需要知道最大的出现次数即可，具体是哪个或哪些位置并不影响最终计算穿过的砖块数量最少的情况。

代码中`seap`字典的命名可能源于作者的个人习惯或随意命名，它用来存储每个砖块右边缘位置的出现次数。为了提高代码的可读性，建议使用更具描述性的名称，例如`edge_count`或`boundary_frequency`，这样的命名更直观地反映了变量的用途和内容。