X Tutup
Skip to content

Commit bee879a

Browse files
author
liwentian
committed
fd
1 parent 542ba19 commit bee879a

File tree

5 files changed

+124
-4
lines changed

5 files changed

+124
-4
lines changed

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -222,7 +222,7 @@
222222
|283|[Move Zeroes](https://leetcode.com/problems/move-zeroes/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/MoveZeroes.java)|100|
223223
|284|[Peeking Iterator](https://leetcode.com/problems/peeking-iterator/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/PeekingIterator.java)|100|
224224
|285|[Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/InorderSuccessorInBST.java)|70|这道题有意思，要多做几遍|
225-
|286|[Walls and Gates](https://leetcode.com/problems/walls-and-gates/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WallsAndGates.java)|70|
225+
|286|[Walls and Gates](https://leetcode.com/problems/walls-and-gates/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WallsAndGates.java)|70|多看两遍|
226226
|287|[Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/FindTheDuplicateNumber.java)||
227227
|288|[Unique Word Abbreviation](https://leetcode.com/problems/unique-word-abbreviation/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/ValidWordAbbr.java)|70|这题不难，多做两遍，题目意思容易理解错|
228228
|295|[Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/FindMedianFromDataStream.java)||
@@ -280,6 +280,7 @@
280280
|398|[Random Pick Index](https://leetcode.com/problems/random-pick-index/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/RandomPickIndex.java)|80|
281281
|401|[Binary Watch](https://leetcode.com/problems/binary-watch/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/BinaryWatch.java)||
282282
|404|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/SumOfLeftLeaves.java)|80|
283+
|406|[Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/QueueReconstructionByHeight.java)|60|这题开始没思路，多做几遍|
283284
|407|[Trapping Rain Water II](https://leetcode.com/problems/trapping-rain-water-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/TrappingRainWaterII.java)||
284285
|409|[Longest Palindrome](https://leetcode.com/problems/longest-palindrome/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/LongestPalindrome.java)||
285286
|410|[Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/SplitArrayLargestSum.java)||

‎google/src/main/java/com/leetcode/google/QueueReconstructionByHeight.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.leetcode.google;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
/**
9+
* Created by liwentian on 2017/9/1.
10+
*/
11+
12+
public class QueueReconstructionByHeight {
13+
14+
public int[][] reconstructQueue(int[][] people) {
15+
Arrays.sort(people,new Comparator<int[]>(){
16+
@Override
17+
public int compare(int[] o1, int[] o2){
18+
return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
19+
}
20+
});
21+
List<int[]> res = new LinkedList<>();
22+
for(int[] cur : people){
23+
res.add(cur[1],cur);
24+
}
25+
return res.toArray(new int[people.length][]);
26+
}
27+
}

‎google/src/main/java/com/leetcode/google/WallsAndGates.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.leetcode.google;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* Created by liwentian on 2017/9/1.
8+
*/
9+
10+
public class WallsAndGates {
11+
12+
public void wallsAndGates(int[][] rooms) {
13+
Queue<int[]> queue = new LinkedList<>();
14+
Queue<int[]> next = new LinkedList<>();
15+
for (int i = 0; i < rooms.length; i++) {
16+
for (int j = 0; j < rooms[0].length; j++) {
17+
if (rooms[i][j] == 0) {
18+
queue.add(new int[] {i, j});
19+
}
20+
}
21+
}
22+
23+
int level = 0;
24+
25+
while (!queue.isEmpty()) {
26+
int[] pos = queue.poll();
27+
int x = pos[0], y = pos[1];
28+
29+
if (rooms[x][y] == Integer.MAX_VALUE) {
30+
rooms[x][y] = level;
31+
}
32+
33+
int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
34+
for (int m = 0; m < dx.length; m++) {
35+
int x0 = x + dx[m], y0 = y + dy[m];
36+
if (x0 < 0 || x0 >= rooms.length || y0 < 0 || y0 >= rooms[0].length) {
37+
continue;
38+
}
39+
if (rooms[x0][y0] != Integer.MAX_VALUE) {
40+
continue;
41+
}
42+
next.add(new int[] {x0, y0});
43+
}
44+
45+
if (queue.isEmpty()) {
46+
queue.addAll(next);
47+
next.clear();
48+
level++;
49+
}
50+
}
51+
}
52+
}

‎solution/src/main/java/com/inuker/solution/QueueReconstructionByHeight.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.inuker.solution;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
/**
9+
* Created by liwentian on 2017/9/1.
10+
*/
11+
12+
/**
13+
* 这题核心思路是：
14+
* 1，先取出高度最高的那一组，如果有若干个高度相同的，则按k升序排列，这就是他们之后的相对顺序了。
15+
* 2，排除刚取出的那些组，从剩余的组中再取出最高的，仍按k升序排列，然后依次插入
16+
*/
17+
18+
/**
19+
* 为什么要这么做呢？先处理较高的，相对顺序就固定了，再往里插较低的时也不会影响较高的组的k值。
20+
* 而高度相同的组，往前排的k肯定会更小，所以我们按k的升序排好就是他们最后的相对顺序了。
21+
*/
22+
public class QueueReconstructionByHeight {
23+
24+
public int[][] reconstructQueue(int[][] people) {
25+
Arrays.sort(people,new Comparator<int[]>(){
26+
@Override
27+
public int compare(int[] o1, int[] o2){
28+
return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
29+
}
30+
});
31+
List<int[]> res = new LinkedList<>();
32+
for(int[] cur : people){
33+
res.add(cur[1],cur);
34+
}
35+
return res.toArray(new int[people.length][]);
36+
}
37+
}

‎test/src/main/java/com/example/Main.java‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import com.leetcode.google.DecodeString;
44
import com.leetcode.google.MissingRanges;
5+
import com.leetcode.google.QueueReconstructionByHeight;
56
import com.leetcode.google.SentenceScreenFitting;
67
import com.leetcode.google.ShortestDistanceFromAllBuildings;
78
import com.leetcode.google.StrobogrammaticNumberII;
@@ -16,9 +17,11 @@
1617
public class Main {
1718

1819
public static void main(String[] args) {
19-
List<String> list = new StrobogrammaticNumberII().findStrobogrammatic(4);
20-
for (String s : list) {
21-
System.out.print(s + " ");
20+
int[][] result = new QueueReconstructionByHeight().reconstructQueue(new int[][] {
21+
{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}
22+
});
23+
for (int[] res : result) {
24+
System.out.println(res[0] + " " + res[1]);
2225
}
2326
}
2427
}

0 commit comments

Comments
 (0)
X Tutup