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大量的集成学习就知道这节肯定绕不过去了. 在这里，仅仅说...

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

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

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

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

• 最通俗易懂的HashMap底层原理图文详解

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

• 【PAT甲级】Course List for Student

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

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

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

• com.sap.ui5.resource.ResourceServlet的工作原理介绍

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