Skip to content

Commit 5aaebae

Browse files
BlankjBlankj
committed
feat: add 554
1 parent 685d089 commit 5aaebae

File tree

8 files changed

+392
-131
lines changed

8 files changed

+392
-131
lines changed

‎README.md

+1
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,7 @@
6060
|3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|
6161
|8|[String to Integer (atoi)][008]|Math, String|
6262
|19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|
63+
|554|[Brick Wall][554]|Hash Table|
6364

6465

6566
## Hard

‎note/554/README.md

+70
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
# [Brick Wall][title]
2+
3+
## Description
4+
5+
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.
6+
7+
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.
8+
9+
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.
10+
11+
**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.**
12+
13+
**Example:**
14+
15+
```
16+
Input:
17+
[[1,2,2,1],
18+
[3,1,2],
19+
[1,3,2],
20+
[2,4],
21+
[3,1,2],
22+
[1,3,1,1]]
23+
Output: 2
24+
```
25+
26+
Explanation:
27+
![img](https://leetcode.com/static/images/problemset/brick_wall.png)
28+
29+
**Note:**
30+
31+
1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
32+
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.
33+
34+
**Tags:** Hash Table
35+
36+
37+
## 思路
38+
39+
题意根据图示已经描述得很清楚了，就是在从底部到顶部，求最少交叉的数量，我们可以把每堵墙可以穿过的地方保存到哈希表中，每次遇到哈希表中的值加一，代表就是这条路不用交叉的数量，最终我们可以算出不用交叉的最大值，让总墙数减去其值就是最少交叉的数量。
40+
41+
``` java
42+
class Solution {
43+
public int leastBricks(List<List<Integer>> wall) {
44+
Map<Integer, Integer> map = new HashMap<>();
45+
int width = 0, max = 0;
46+
for (List<Integer> sub : wall) {
47+
int p = 0;
48+
for (int i = 0, len = sub.size() - 1; i < len; ++i) {
49+
p += sub.get(i);
50+
Integer v = map.get(p);
51+
map.put(p, (v == null ? 0 : v) + 1);
52+
}
53+
}
54+
for (Integer integer : map.values()) {
55+
if (integer > max) max = integer;
56+
}
57+
return wall.size() - max;
58+
}
59+
}
60+
```
61+
62+
63+
## 结语
64+
65+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
66+
67+
68+
69+
[title]: https://leetcode.com/problems/brick-wall
70+
[ajl]: https://github.com/Blankj/awesome-java-leetcode

‎project/leetcode/.idea/workspace.xml

+271-93
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎project/leetcode/out/production/leetcode/com/blankj/medium/_019/Solution$ListNode.class

-972 Bytes
Binary file not shown.

‎project/leetcode/out/production/leetcode/com/blankj/medium/_019/Solution.class

-573 Bytes
Binary file not shown.

‎project/leetcode/out/production/leetcode/com/blankj/medium/_554/Solution.class

2.59 KB
Binary file not shown.

‎project/leetcode/src/com/blankj/medium/_019/Solution.java

+4-38
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package com.blankj.medium._019;
22

3+
import com.blankj.structure.ListNode;
4+
35
/**
46
* <pre>
57
* author: Blankj
@@ -9,27 +11,6 @@
911
* </pre>
1012
*/
1113
public class Solution {
12-
13-
static class ListNode {
14-
int val;
15-
ListNode next;
16-
17-
ListNode(int x) {
18-
val = x;
19-
}
20-
21-
@Override
22-
public String toString() {
23-
String str = "[" + String.valueOf(val);
24-
ListNode p = next;
25-
while (p != null) {
26-
str += ", " + String.valueOf(p.val);
27-
p = p.next;
28-
}
29-
return str + "]";
30-
}
31-
}
32-
3314
public ListNode removeNthFromEnd(ListNode head, int n) {
3415
ListNode pre = head;
3516
ListNode afterPreN = head;
@@ -50,22 +31,7 @@ public ListNode removeNthFromEnd(ListNode head, int n) {
5031

5132
public static void main(String[] args) {
5233
Solution solution = new Solution();
53-
ListNode listNode0 = new ListNode(1);
54-
ListNode listNode1 = new ListNode(2);
55-
ListNode listNode2 = new ListNode(3);
56-
ListNode listNode3 = new ListNode(4);
57-
ListNode listNode4 = new ListNode(5);
58-
listNode0.next = listNode1;
59-
listNode1.next = listNode2;
60-
listNode2.next = listNode3;
61-
listNode3.next = listNode4;
62-
listNode4.next = null;
63-
System.out.println(listNode0.toString());
64-
System.out.println(solution.removeNthFromEnd(listNode0, 2).toString());
65-
66-
ListNode listNode5 = new ListNode(1);
67-
System.out.println(listNode5.toString());
68-
ListNode res = solution.removeNthFromEnd(listNode5, 1);
69-
System.out.println(res == null ? "[]" : res.toString());
34+
ListNode.print(solution.removeNthFromEnd(ListNode.createTestData("[1,2,3,4,5]"), 2));
35+
ListNode.print(solution.removeNthFromEnd(ListNode.createTestData("[1]"), 1));
7036
}
7137
}

‎project/leetcode/src/com/blankj/medium/_554/Solution.java

+46
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.blankj.medium._554;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.HashMap;
6+
import java.util.List;
7+
import java.util.Map;
8+
9+
/**
10+
* <pre>
11+
* author: Blankj
12+
* blog : http://blankj.com
13+
* time : 2017/10/13
14+
* desc :
15+
* </pre>
16+
*/
17+
public class Solution {
18+
public int leastBricks(List<List<Integer>> wall) {
19+
Map<Integer, Integer> map = new HashMap<>();
20+
int width = 0, max = 0;
21+
for (List<Integer> sub : wall) {
22+
int p = 0;
23+
for (int i = 0, len = sub.size() - 1; i < len; ++i) {
24+
p += sub.get(i);
25+
Integer v = map.get(p);
26+
map.put(p, (v == null ? 0 : v) + 1);
27+
}
28+
}
29+
for (Integer integer : map.values()) {
30+
if (integer > max) max = integer;
31+
}
32+
return wall.size() - max;
33+
}
34+
35+
public static void main(String[] args) {
36+
Solution solution = new Solution();
37+
List<List<Integer>> list = new ArrayList<>();
38+
list.add(Arrays.asList(1, 2, 2, 1));
39+
list.add(Arrays.asList(3, 1, 2));
40+
list.add(Arrays.asList(1, 3, 2));
41+
list.add(Arrays.asList(2, 4));
42+
list.add(Arrays.asList(3, 1, 2));
43+
list.add(Arrays.asList(1, 3, 1, 1));
44+
System.out.println(solution.leastBricks(list));
45+
}
46+
}

0 commit comments

Comments
 (0)