554.砖墙
https://leetcode-cn.com/problems/brick-wall/
难度：中等
题目：
你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。
你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。
你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
提示：
- 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
示例：
示例 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
分析
初看这道题，首先思考砖墙的总长度对于二维数组的每个子数组都是相同的。
那么遍历每个数组，找到停止的位置，就加一，然后获取最终结果。
class Solution:
def leastBricks(self, wall):
total = sum(wall[0])
ret = len(wall)
d = {i:0 for i in range(total -1)}
for i in wall:
tmp = 0
for j in i:
while j > 0:
if j != 1:
d[tmp] += 1
j -= 1
tmp += 1
return min(d.values()) if d else ret
按照这种方式，基础的用例过了，但遇到如下用例就傻眼了...
[[100000000],[100000000],[100000000]]
想想其实思路已经对了一般，只需要再优化下就好了。
上面的例子，我是通过循环遍历砖墙总长度，造成了很多不必要的循环，其实我们可以使用前缀和的方式去解决。
这样就能极大缩短循环的时间，从原有的len(砖墙长度)转变为len(每个数组的长度)，比如刚才的用例，
之前方法我们需要计算3*100000000，而现在我们只需要计算三次即可。
这里还有一个细节，用例二中每个子数组长度都为1，那么结果就是wall的长度，不然我们就不是穿墙，饶是绕墙了。
解题：
class Solution:
def leastBricks(self, wall):
ret = len(wall)
d = {}
for li in wall:
for i in range(len(li) - 1):
if i != 0:
li[i] = li[i - 1] + li[i]
d[li[i]] = d.get(li[i], 0) + 1
return ret-max(d.values()) if d else ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
