X

LEETCODE 554. Brick Wall 解题思路分析

题目大意:

砖墙

你的面前有一堵方形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。

如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。

你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

示例:

输入: [[1,2,2,1],
            [3,1,2],
            [1,3,2],
            [2,4],
            [3,1,2],
            [1,3,1,1]]
输出: 2
解释:

提示:

  • 每一行砖块的宽度之和应该相等,并且不能超过 INT_MAX。
  • 每一行砖块的数量在 [1,10,000] 范围内, 墙的高度在 [1,10,000] 范围内, 总的砖块数量不超过 20,000。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=554

解题思路分析:

这道题我们可以使用统计砖块边缘的方法,查看每块砖右侧边缘所在的位置,最后统计出最多的所在位置相同的砖块的数量,这也代表了从该位置划线穿越的砖块数量最少。另外注意一点,根据题目最后一句的提示,每行最后一块砖的位置是不能参与统计的。

实现代码:

public int leastBricks(List<List<Integer>> wall) {
    Map<Integer, Integer> map=new HashMap<>(); // 统计每块砖的位置
    for(List<Integer> list : wall){ // 循环每一行
        int x=0; // 当前砖块右侧所在位置
        for(int i=0;i<list.size()-1;i++){ // 循环每一块砖(最后一块砖不参与统计)
            x+=list.get(i); // 当前砖块右侧位置
            int count=map.getOrDefault(x, 0); // 更新该位置下砖块数量
            map.put(x,count+1);
        }
    }
    int maxCount=0; // 相同位置下,砖块数量最多的值
    for(int key:map.keySet()){
        maxCount=Math.max(maxCount,map.get(key));
    }
    return wall.size()-maxCount;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 83.12% of Java online submissions for Brick Wall.

Memory Usage: 41.7 MB, less than 100.00% of Java online submissions for Brick Wall.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-554-brick-wall-解题思路分析/
Categories: leetcode
kwantong: