|3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|

|8|[String to Integer (atoi)][008]|Math, String|

|19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|

|554|[Brick Wall][554]|Hash Table|

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:**

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.

**Tags:** Hash Table

题意根据图示已经描述得很清楚了，就是在从底部到顶部，求最少交叉的数量，我们可以把每堵墙可以穿过的地方保存到哈希表中，每次遇到哈希表中的值加一，代表就是这条路不用交叉的数量，最终我们可以算出不用交叉的最大值，让总墙数减去其值就是最少交叉的数量。

classSolution {

publicintleastBricks(List<List<Integer>>wall) {

Map<Integer,Integer> map=newHashMap<>();

int width=0, max=0;

for (List<Integer> sub: wall) {

int p=0;

for (int i=0, len= sub.size()-1; i< len;++i) {

p+= sub.get(i);

Integer v= map.get(p);

map.put(p, (v==null?0: v)+1);

}

}

for (Integer integer: map.values()) {

if (integer> max) max= integer;

}

return wall.size()- max;

}

}

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]

[title]:https://leetcode.com/problems/brick-wall

[ajl]:https://github.com/Blankj/awesome-java-leetcode

packagecom.blankj.medium._019;

importcom.blankj.structure.ListNode;

publicclassSolution {

staticclassListNode {

intval;

ListNodenext;

ListNode(intx) {

val =x;

}

publicStringtoString() {

Stringstr ="[" +String.valueOf(val);

ListNodep =next;

while (p !=null) {

str +=", " +String.valueOf(p.val);

p =p.next;

}

returnstr +"]";

}

}

publicListNoderemoveNthFromEnd(ListNodehead,intn) {

ListNodepre =head;

ListNodeafterPreN =head;

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

ListNodelistNode0 =newListNode(1);

ListNodelistNode1 =newListNode(2);

ListNodelistNode2 =newListNode(3);

ListNodelistNode3 =newListNode(4);

ListNodelistNode4 =newListNode(5);

listNode0.next =listNode1;

listNode1.next =listNode2;

listNode2.next =listNode3;

listNode3.next =listNode4;

listNode4.next =null;

System.out.println(listNode0.toString());

System.out.println(solution.removeNthFromEnd(listNode0,2).toString());

ListNodelistNode5 =newListNode(1);

System.out.println(listNode5.toString());

ListNoderes =solution.removeNthFromEnd(listNode5,1);

System.out.println(res ==null ?"[]" :res.toString());

ListNode.print(solution.removeNthFromEnd(ListNode.createTestData("[1,2,3,4,5]"),2));

ListNode.print(solution.removeNthFromEnd(ListNode.createTestData("[1]"),1));

}

}

packagecom.blankj.medium._554;

importjava.util.ArrayList;

importjava.util.Arrays;

importjava.util.HashMap;

importjava.util.List;

importjava.util.Map;

publicclassSolution {

publicintleastBricks(List<List<Integer>>wall) {

Map<Integer,Integer>map =newHashMap<>();

intwidth =0,max =0;

for (List<Integer>sub :wall) {

intp =0;

for (inti =0,len =sub.size() -1;i <len; ++i) {

p +=sub.get(i);

Integerv =map.get(p);

map.put(p, (v ==null ?0 :v) +1);

}

}

for (Integerinteger :map.values()) {

if (integer >max)max =integer;

}

returnwall.size() -max;

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

List<List<Integer>>list =newArrayList<>();

list.add(Arrays.asList(1,2,2,1));

list.add(Arrays.asList(3,1,2));

list.add(Arrays.asList(1,3,2));

list.add(Arrays.asList(2,4));

list.add(Arrays.asList(3,1,2));

list.add(Arrays.asList(1,3,1,1));

System.out.println(solution.leastBricks(list));

}

}