力扣554(java&python)-砖墙（中等）

题目：

你的面前有一堵矩形的、由 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 <= 10⁴
• 1 <= wall[i].length <= 10⁴
• 1 <= sum(wall[i].length) <= 2 * 10⁴
• 对于每一行 i ，sum(wall[i]) 是相同的
• 1 <= wall[i][j] <= 2³¹ – 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/brick-wall
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

参考题解：@【97wglL4】

哈希表+前缀和：题目要求的是要求穿过的砖块数量最少，那么可以等效的求穿过的空隙最多。使用哈希表统计每个空隙出现的次数，然后统计出现次数最多的间隙，最终用砖块的总行数减去最大空隙数即为穿过的最小砖块数。

例如示例1：

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

输出：2

根据上面砖块平铺的示意图，间隙数就是每个砖块的右边界【不能计算最后一块砖的右边界】，而每个砖块的右边界等价于求每块砖的前缀和，所以用一个变量sum去维护每一行的前缀和，然后再用一个map做统计就可以了。
注意：x = 0和右边缘不能算。

• 第一行的间隙数[1,3,5]
• 第二行的间隙数[3,4]
• 第三行的间隙数[1,4]
• 第四行的间隙数[2]
• 第五行的间隙数[3,4]
• 第六行的间隙数[1,4,5]

出现间隙数最多的是4，用总行6 – 4 = 2。

java代码：

 1 class Solution {
 2     public int leastBricks(List<List<Integer>> wall) {
 3         Map<Integer, Integer> map = new HashMap<>();
 4         int  maxcount = 0;
 5         for(List<Integer> list : wall){
 6             int sum = 0;
 7             int n = list.size();
 8             for(int i = 0; i < n-1; i++){
 9                 sum += list.get(i);
10                 int count = map.getOrDefault(sum, 0) + 1;
11                 map.put(sum, count);
12                 maxcount = Math.max(maxcount, count);
13             }
14         }
15         return wall.size() - maxcount;
16 
17     }
18 }

 python3代码：

 1 class Solution:
 2     def leastBricks(self, wall: List[List[int]]) -> int:
 3         map = collections.defaultdict(int)
 4         for line in wall:
 5             sum = 0
 6             for i in line[:-1]:
 7                 sum += i
 8                 map[sum] += 1
 9         # 如果map为空，wall = [[1],[1],[1]]则每块砖都穿过
10         if not map:
11             return len(wall)
12         return len(wall) - max(map.values(), default = 0)

 小知识：

1.python中切片：假设str = ‘012345678’

str[:-1]：正向输出，从开始到倒数第一个字符（不含这倒数第一个） # 01234567

2.在使用 python 自带的字典 dict() 时常会碰到比较麻烦的地方, 譬如当 ‘key1’ 不存在时, 使用 map[key1] 会导致 KeyError. 因此引入 collections.defaultdict()：

这里面的参数可以选择int，dict，set， list， str，将规定 defaultdict 中 value 的默认数值类型， 也就是说，当 ‘key1’ 不存在时, map[key1] 将会返回对应的空值 (int: 0, dict: {}, list: ())。

3.java中getOrDefault()方法:getOrDefault(key, default)如果存在key, 则返回其对应的value, 否则返回给定的默认值

eg:map.getOrDefault(s1.charAt(i), 0) + 1); 若没有s1中的字符就是0, 若有s1中的字符就是在原有值上+1

原文地址：http://www.cnblogs.com/liu-myu/p/16787347.html