leetcode554. Brick Wall

题目要求

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Input:

    [[1,2,2,1],
    [3,1,2],
    [1,3,2],
    [2,4],
    [3,1,2],
    [1,3,1,1]]

Output: 2

Explanation:

Note:

  1. The width sum of bricks in different rows are the same and won't exceed INT_MAX。
  2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

现在有一个二维数组来表示一面墙,其中二维数组中每一个值代表某一行的一颗砖块的长度。现在会画一条垂直的线,问最少需要跨过多块砖。

思路和代码

本质上就是记录一下经过的所有砖块缝隙,然后遇到重复的砖块缝隙就将该为止的砖块缝隙数量加一。最后穿过越多的砖块缝隙代表所需要穿过的砖块数量越少。

public int leastBricks(List<List<Integer>> wall) {  
    Map<Integer, Integer> map = new HashMap<>();  
    int row = wall.size();  
    int maxEdge = 0;  
    for (List<Integer> bricks : wall) {  
        int sumOfBrick = 0;  
        for (int i = 0; i < bricks.size() - 1; i++) {  
            int brick = bricks.get(i);  
            sumOfBrick += brick;  
            int edge = map.getOrDefault(sumOfBrick, 0) + 1;  
            map.put(sumOfBrick, edge);  
            maxEdge = Math.max(edge, maxEdge);  
        }  
    }  
    return row - maxEdge;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode452. Minimum Number of Arrows to Burst Balloons

    There are a number of spherical balloons spread in two-dimensional space. For ea...

    眯眯眼的猫头鹰
  • leetcode543. Diameter of Binary Tree

    Given a binary tree, you need to compute the length of the diameter of the tree....

    眯眯眼的猫头鹰
  • leetcode467. Unique Substrings in Wraparound String

    假设存在一个从a-z26个字母无限循环的字符串s,现在输入一个字符串p,问该字符串有多少个子字符串在s中循环出现?

    眯眯眼的猫头鹰
  • 机器学习实战 | 第三章:集成学习

    集成学习肯定是在实战中最不可或缺的思想了.毕竟都想把错误率低一点,再低一点,再低一点.看看kaggle大量的集成学习就知道这节肯定绕不过去了. 在这里,仅仅说...

    用户1332428
  • SAP CRM附件在应用服务器上的存储原理解析

    Content Management(CM) was introduced in basis release 6.10 and implemented in C...

    Jerry Wang
  • MCC:用PNML格式展开彩色培养网的工具(CS)

    在本文中,我们介绍了MCC,MCC是为一项非常具体的任务设计的工具:将PNML语法中给出的高级Petri网模型转换为等效的Place/Transition网。 ...

    时代在召唤
  • 最通俗易懂的HashMap底层原理图文详解

    HashMap里面涉及了很多的知识点,可以比较全面考察面试者的基本功,想要拿到一个好offer,这是一个迈不过的坎,接下来我们用最通俗易懂的语言带着大家揭开Ha...

    一个会写诗的程序员
  • 【PAT甲级】Course List for Student

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决

    这句话几乎概括了计算机软件体系结构的设计要点.整个体系从上到下都是按照严格的层级结构设计的.

    一个会写诗的程序员
  • com.sap.ui5.resource.ResourceServlet的工作原理介绍

    There is one question asking how and where the js file “resources/sap-ui-core.js...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券