【LeetCode】砖墙 Java 题解

关注

发布于: 2021 年 05 月 02 日

题目描述

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

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

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

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

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

复制代码

思路

今天的每日一题，题目虽然比较长，需要认真分析。
认真分析，可以得出一个显而易见的结论，垂线穿过的砖块 + 边缘穿过的砖块 = 所有砖块的高度。

AC 代码

class Solution {    public int leastBricks(List<List<Integer>> wall) {        Map<Integer, Integer> cnt = new HashMap<>();        for (List<Integer> widths : wall) {            int n = widths.size();            int sum = 0;            for (int i = 0; i < n - 1; i++) {                sum += widths.get(i);                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);            }        }        int maxCnt = 0;        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {            maxCnt = Math.max(maxCnt, entry.getValue());        }        return wall.size() - maxCnt;    }}

复制代码

总结

上述代码的时间复杂度是 O(m * n), 空间复杂度是 O (m * n)
遇到题目比较长的问题，需要认真分析，可以通过画图等方式，帮助理解题目！
坚持每日一题，加油！

发布于: 2021 年 05 月 02 日阅读数: 6

原文链接:【http://xie.infoq.cn/article/3d54f16679bde28802adebc9e】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】砖墙 Java 题解

题目描述

思路

AC 代码

总结

HQ数字卡

评论