Skip to content

Commit d70ff0b

Browse files
awangdevawangdev
committed
3.21
1 parent 50e83db commit d70ff0b

File tree

7 files changed

+130
-148
lines changed

7 files changed

+130
-148
lines changed

‎Java/Course Schedule II.java

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -6,11 +6,14 @@
66
/*
77
There are a total of n courses you have to take, labeled from 0 to n - 1.
88
9-
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
9+
Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
10+
which is expressed as a pair: [0,1]
1011
11-
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
12+
Given the total number of courses and a list of prerequisite pairs,
13+
return the ordering of courses you should take to finish all courses.
1214
13-
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
15+
There may be multiple correct orders, you just need to return one of them.
16+
If it is impossible to finish all courses, return an empty array.
1417
1518
For example:
1619

‎Java/Course Schedule.java

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,21 @@
11
M
22

3-
有点绕，但是做过一次就明白一点。
4-
是topological sort的题目。一般都是给有dependency的东西排序。
3+
有点绕，但是做过一次就明白一点。
4+
是topological sort的题目。一般都是给有dependency的东西排序。
55

6-
最终都会到一个sink node， 再不会有向后的dependency, 在那个点截止。
7-
我就已这样子的点为map的key, 然后value是以这个node为prerequisite的 list of courses.
6+
最终都会到一个sink node， 再不会有向后的dependency, 在那个点截止。
7+
我就已这样子的点为map的key, 然后value是以这个node为prerequisite的 list of courses.
88

9-
画个图的话，prerequisite都是指向那个sink node， 然后我们在组成map的时候，都是从sink node 发散回来到dependent nodes.
9+
画个图的话，prerequisite都是指向那个sink node， 然后我们在组成map的时候，都是从sink node 发散回来到dependent nodes.
1010

11-
在DFS里面，我们是反向的， 然后，最先完全visited的那个node, 肯定是最左边的node了，它被mark的seq也是最高的。
11+
在DFS里面，我们是反向的， 然后，最先完全visited的那个node, 肯定是最左边的node了，它被mark的seq也是最高的。
1212

13-
而我们的sink node，当它所有的支线都visit完了，seq肯定都已经减到最小了，也就是0，它就是第一个被visit的。
13+
而我们的sink node，当它所有的支线都visit完了，seq肯定都已经减到最小了，也就是0，它就是第一个被visit的。
1414

1515

16+
最终结果：
17+
每个有pre-requisit的node都trace上去（自底向上），并且都没有发现cycle.也就说明schedule可以用了。
18+
1619
```
1720
/*
1821
There are a total of n courses you have to take, labeled from 0 to n - 1.

‎Java/Jump Game II.java

Lines changed: 61 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,22 @@
1+
H
2+
3+
Greedy, 图解 http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
4+
5+
维护一个range, 是最远我们能走的.
6+
7+
index/i 是一步一步往前, 每次当 i <= range, 做一个while loop， 在其中找最远能到的地方 maxRange
8+
9+
然后更新 range = maxRange
10+
11+
其中step也是跟index是一样, 一步一步走.
12+
13+
最后check的condition是，我们最远你能走的range >= nums.length - 1, 说明以最少的Step就到达了重点。Good.
14+
15+
16+
```
117
/*
2-
Given an array of non-negative integers, you are initially positioned at the first index of the array.
18+
Given an array of non-negative integers,
19+
you are initially positioned at the first index of the array.
320
421
Each element in the array represents your maximum jump length at that position.
522
@@ -8,19 +25,58 @@
825
Example
926
Given array A = [2,3,1,1,4]
1027
11-
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
28+
The minimum number of jumps to reach the last index is 2.
29+
(Jump 1 step from index 0 to 1, then 3 steps to the last index.)
1230
1331
Tags Expand
1432
Greedy Array
1533
34+
*/
35+
36+
/*
37+
3.18 recap.
38+
Wihtin farest we can go, renew farest we can go, renew number of steps.
39+
http://blog.csdn.net/havenoidea/article/details/11853301
40+
41+
图解：
42+
http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
43+
*/
44+
//Greedy. Within max range we can jump to, do another loop to renew the max we can go.
45+
public class Solution {
46+
public int jump(int[] nums) {
47+
if (nums == null || nums.length <= 1) {
48+
return 0;
49+
}
50+
int index = 0;
51+
int step = 0;
52+
int range = 0;
53+
int maxRange = 0;
54+
55+
while (index < nums.length) {
56+
if (range >= nums.length - 1) {
57+
break;
58+
}
59+
while (index <= range) {
60+
maxRange = Math.max(maxRange, index + nums[index]);
61+
index++;
62+
}
63+
range = maxRange;
64+
step++;
65+
}
66+
return step;
67+
}
68+
}
69+
70+
71+
/*
72+
1673
Thanks to Yu’s Garden blog
1774
Thinking process:
1875
0. Use two pointers pStart and pEnd to track the potential locations we can move to.
1976
Consider a range from current spot to the farthest spot: try to find a max value from this range, and see if the max can reach the tail of array.
2077
If no max can read the tail of array, that means we need to move on. At this point, let pStart = pEnd + 1. At same time, move pEnd to the max spot we can go to. Since pEnd moves forward, we could step++
2178
If max reach the tail of array, return the steps.
2279
*/
23-
2480
public class Solution {
2581
/**
2682
* @param A: A list of lists of integers
@@ -55,3 +111,5 @@ public int jump(int[] A) {
55111
//Also DP from nineChapter:
56112
http://www.ninechapter.com/solutions/jump-game-ii/
57113

114+
115+
```

‎Java/Jump Game.java

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,16 @@
1+
M
2+
3+
给出步数，看能不能reach to end.
4+
5+
Status:
6+
DP[i]: 在i点记录，i点之前的步数是否可以走到i点？ True of false.
7+
其实j in [0~i)中间只需要一个能到达i 就好了
8+
Function:
9+
DP[i] = DP[j] && (j + A[j]), for all j in [0 ~ i)
10+
Return:
11+
DP[dp.length - 1];
12+
13+
```
114
/*
215
Given an array of non-negative integers, you are initially positioned at the first index of the array.
316
@@ -31,7 +44,7 @@ public boolean canJump(int[] A) {
3144
if (A == null || A.length == 0) {
3245
return false;
3346
}
34-
//By default, boolean[] can is all false
47+
//By default, boolean[] can is all false
3548
boolean[] can = new boolean[A.length];
3649
can[0] = true;
3750
for (int i = 1; i < A.length; i++) {
@@ -80,3 +93,5 @@ public boolean canJump(int[] A) {
8093
}
8194
}
8295

96+
97+
```

‎Java/Number of Islands II.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,10 @@
11
H
22

3+
用HashMap的Union-find.
4+
5+
把board转换成1D array， 就可以用union-find来判断了。 判断时，是在四个方向各走一步，判断是否是同一个Land.
6+
7+
每走一次operator，都会count++. 若发现是同一个island, count--
38

49
```
510
/*

‎Java/Number of Islands.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
只不过这个不Return list, 而只是# of islands
88

99
```
10-
/*
10+
/*in
1111
Given a boolean 2D matrix, find the number of islands.
1212
1313
Example

‎ReviewPage.md

Lines changed: 31 additions & 133 deletions
Original file line numberDiff line numberDiff line change
@@ -878,19 +878,22 @@ value-1就是说，找比自己所在range小1的range（那么自然而然地
878878
---
879879
**68. [Course Schedule.java](https://github.com/shawnfan/LintCode/blob/master/Java/Course Schedule.java)** Level: Medium
880880

881-
有点绕，但是做过一次就明白一点。
882-
是topological sort的题目。一般都是给有dependency的东西排序。
881+
有点绕，但是做过一次就明白一点。
882+
是topological sort的题目。一般都是给有dependency的东西排序。
883883

884-
最终都会到一个sink node， 再不会有向后的dependency, 在那个点截止。
885-
我就已这样子的点为map的key, 然后value是以这个node为prerequisite的 list of courses.
884+
最终都会到一个sink node， 再不会有向后的dependency, 在那个点截止。
885+
我就已这样子的点为map的key, 然后value是以这个node为prerequisite的 list of courses.
886886

887-
画个图的话，prerequisite都是指向那个sink node， 然后我们在组成map的时候，都是从sink node 发散回来到dependent nodes.
887+
画个图的话，prerequisite都是指向那个sink node， 然后我们在组成map的时候，都是从sink node 发散回来到dependent nodes.
888888

889-
在DFS里面，我们是反向的， 然后，最先完全visited的那个node, 肯定是最左边的node了，它被mark的seq也是最高的。
889+
在DFS里面，我们是反向的， 然后，最先完全visited的那个node, 肯定是最左边的node了，它被mark的seq也是最高的。
890890

891-
而我们的sink node，当它所有的支线都visit完了，seq肯定都已经减到最小了，也就是0，它就是第一个被visit的。
891+
而我们的sink node，当它所有的支线都visit完了，seq肯定都已经减到最小了，也就是0，它就是第一个被visit的。
892892

893893

894+
最终结果：
895+
每个有pre-requisit的node都trace上去（自底向上），并且都没有发现cycle.也就说明schedule可以用了。
896+
894897

895898
---
896899
**69. [Data Stream Median.java](https://github.com/shawnfan/LintCode/blob/master/Java/Data Stream Median.java)** Level: Hard
@@ -2447,144 +2450,34 @@ HashMap 来确认match。有几种情况考虑:
24472450

24482451

24492452
---
2450-
**132. [Jump Game II.java](https://github.com/shawnfan/LintCode/blob/master/Java/Jump Game II.java)**Given an array of non-negative integers, you are initially positioned at the first index of the array.
2451-
2452-
Each element in the array represents your maximum jump length at that position.
2453+
**132. [Jump Game II.java](https://github.com/shawnfan/LintCode/blob/master/Java/Jump Game II.java)** Level: Hard
24532454

2454-
Your goal is to reach the last index in the minimum number of jumps.
2455-
2456-
Example
2457-
Given array A = [2,3,1,1,4]
2455+
Greedy, 图解 http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
24582456

2459-
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
2457+
维护一个range, 是最远我们能走的.
24602458

2461-
Tags Expand
2462-
Greedy Array
2459+
index/i 是一步一步往前, 每次当 i <= range, 做一个while loop， 在其中找最远能到的地方 maxRange
24632460

2464-
Thanks to Yu’s Garden blog
2465-
Thinking process:
2466-
0. Use two pointers pStart and pEnd to track the potential locations we can move to.
2467-
Consider a range from current spot to the farthest spot: try to find a max value from this range, and see if the max can reach the tail of array.
2468-
If no max can read the tail of array, that means we need to move on. At this point, let pStart = pEnd + 1. At same time, move pEnd to the max spot we can go to. Since pEnd moves forward, we could step++
2469-
If max reach the tail of array, return the steps.
2470-
*/
2461+
然后更新 range = maxRange
24712462

2472-
public class Solution {
2473-
/**
2474-
* @param A: A list of lists of integers
2475-
* @return: An integer
2476-
*/
2477-
public int jump(int[] A) {
2478-
if (A == null || A.length == 0) {
2479-
return 0;
2480-
}
2481-
int pStart = 0;
2482-
int pEnd = 0;
2483-
int steps = 0;
2484-
while (pEnd < A.length - 1) {
2485-
steps++; //Cound step everytime when pEnd is moving to the farthest.
2486-
int farthest = 0;
2487-
//Find farest possible and see if reach the tail
2488-
for (int i = pStart; i <= pEnd; i++) {
2489-
farthest = Math.max(farthest, i + A[i]);
2490-
if (farthest >= A.length - 1) {
2491-
return steps;
2492-
}
2493-
}
2494-
//Re-select pointer position for start and end
2495-
pStart = pEnd + 1;
2496-
pEnd = farthest;
2497-
}
2498-
return -1; //This is the case where no solution can be found.
2499-
}
2500-
}
2463+
其中step也是跟index是一样, 一步一步走.
25012464

2465+
最后check的condition是，我们最远你能走的range >= nums.length - 1, 说明以最少的Step就到达了重点。Good.
25022466

2503-
//Also DP from nineChapter:
2504-
http://www.ninechapter.com/solutions/jump-game-ii/
25052467

25062468

25072469
---
2508-
**133. [Jump Game.java](https://github.com/shawnfan/LintCode/blob/master/Java/Jump Game.java)**Given an array of non-negative integers, you are initially positioned at the first index of the array.
2509-
2510-
Each element in the array represents your maximum jump length at that position.
2470+
**133. [Jump Game.java](https://github.com/shawnfan/LintCode/blob/master/Java/Jump Game.java)** Level: Medium
25112471

2512-
Determine if you are able to reach the last index.
2472+
给出步数，看能不能reach to end.
25132473

2514-
Example
2515-
A = [2,3,1,1,4], return true.
2516-
2517-
A = [3,2,1,0,4], return false.
2518-
2519-
This can be done using DP. However, greedy algorithm is fast in this particular problem. Consider both solutions.
2520-
2521-
DP
2522-
Thinking Process:
2523-
We have array A, that stores the # of steps for each index.
2524-
State: f[i] means if previous steps can reach to i. True/False
2525-
Function: f[i] = f[j] && (j + A[j] >= i)
2526-
Init: f[0] = true
2527-
Answer: f[n-1], if n is the length of A
2528-
*/
2529-
2530-
public class Solution {
2531-
/**
2532-
* @param A: A list of integers
2533-
* @return: The boolean answer
2534-
**/
2535-
//DP
2536-
public boolean canJump(int[] A) {
2537-
if (A == null || A.length == 0) {
2538-
return false;
2539-
}
2540-
//By default, boolean[] can is all false
2541-
boolean[] can = new boolean[A.length];
2542-
can[0] = true;
2543-
for (int i = 1; i < A.length; i++) {
2544-
for (int j = 0; j < i; j++) {
2545-
if (A[j] && (j + A[j] >= i)) {
2546-
can[i] = true;
2547-
break;
2548-
}
2549-
}
2550-
}
2551-
return can[A.length - 1];
2552-
}
2553-
}
2554-
2555-
2556-
2557-
/*
2558-
2559-
Greedy. Ideas from Yu’s Garden
2560-
At each index, check how far we can jump, store this forest-can-jump position in variable ‘farest’. Take max of current farest and (index + A[index]), store is in farest
2561-
At each index, compare if ‘farest’ is greater than the end of array, if so, found solution, return true.
2562-
At each index, also check if ‘farest == current index’, that means the farest we can move is to current index and we cannot move forward. Then return false.
2563-
*/
2564-
2565-
public class Solution {
2566-
/**
2567-
* @param A: A list of integers
2568-
* @return: The boolean answer
2569-
**/
2570-
2571-
public boolean canJump(int[] A) {
2572-
if (A == null || A.length == 0) {
2573-
return false;
2574-
}
2575-
int farest = 0;
2576-
for (int i = 0; i < A.length; i++) {
2577-
farest = Math.max(farest, i + A[i]);
2578-
if (farest > A.length - 1) {
2579-
return true;
2580-
}
2581-
if (farest == i) {
2582-
return false;
2583-
}
2584-
}
2585-
return true;
2586-
}
2587-
}
2474+
Status:
2475+
DP[i]: 在i点记录，i点之前的步数是否可以走到i点？ True of false.
2476+
其实j in [0~i)中间只需要一个能到达i 就好了
2477+
Function:
2478+
DP[i] = DP[j] && (j + A[j]), for all j in [0 ~ i)
2479+
Return:
2480+
DP[dp.length - 1];
25882481

25892482

25902483
---
@@ -4136,6 +4029,11 @@ node 到底，而head ~ node刚好是 n 距离。所以head就是要找的last n
41364029
---
41374030
**198. [Number of Islands II.java](https://github.com/shawnfan/LintCode/blob/master/Java/Number of Islands II.java)** Level: Hard
41384031

4032+
用HashMap的Union-find.
4033+
4034+
把board转换成1D array， 就可以用union-find来判断了。 判断时，是在四个方向各走一步，判断是否是同一个Land.
4035+
4036+
每走一次operator，都会count++. 若发现是同一个island, count--
41394037

41404038

41414039
---

0 commit comments

Comments
 (0)