8000 Merge pull request #26 from HbnKing/dev · HbnKing/Algorithm@1e98502 · GitHub
[go: up one dir, main page]
Skip to content

Commit 1e98502

Browse files
HbnKingHbnKing
authored
Merge pull request #26 from HbnKing/dev
Dev
2 parents 48263b6 + e3e3675 commit 1e98502

File tree

3 files changed

+251
-2
lines changed

3 files changed

+251
-2
lines changed

‎LeetCode/README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -303,7 +303,7 @@
303303
|58|[Length of Last Word](https://oj.leetcode.com/problems/length-of-last-word/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/lengthOfLastWord/lengthOfLastWord), [Scala](./algorithms/java/src/lengthOfLastWord/LengthOfLastWord.java)|Easy|
304304
|57|[Insert Interval](https://oj.leetcode.com/problems/insert-interval/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/insertInterval/insertInterval)|Hard|
305305
|56|[Merge Intervals](https://oj.leetcode.com/problems/merge-intervals/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/mergeIntervals/mergeIntervals)|Hard|
306-
|55|[Jump Game](https://oj.leetcode.com/problems/jump-game/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/jumpGame/jumpGame)|Medium|
306+
|55|[Jump Game](https://oj.leetcode.com/problems/jump-game/)| [Java](./src/main/java/indi/ours/algorithm/leetcode/algorithms/_55.java)|Medium|O(n) | O(1)|Q45 |
307307
|54|[Spiral Matrix](https://oj.leetcode.com/problems/spiral-matrix/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java)|Medium|
308308
|53|[Maximum Subarray](https://oj.leetcode.com/problems/maximum-subarray/)| [Java](./src/main/java/indi/ours/algorithm/leetcode/algorithms/_53.java)|Medium|Array <br> Dynamic Programming <br> Divide and Conquer | O(n) |
309309
|52|[N-Queens II](https://oj.leetcode.com/problems/n-queens-ii/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/nQueens/nQueuens.II)|Hard|
@@ -313,7 +313,7 @@
313313
|48|[Rotate Image](https://oj.leetcode.com/problems/rotate-image/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/rotateImage/rotateImage)|Medium|
314314
|47|[Permutations II](https://oj.leetcode.com/problems/permutations-ii/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/permutations/permutations.II)|Hard|
315315
|46|[Permutations](https://oj.leetcode.com/problems/permutations/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/permutations/permutations)|Medium|
316-
|45|[Jump Game II](https://oj.leetcode.com/problems/jump-game-ii/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/jumpGame/jumpGame.II)|Hard|
316+
|45|[Jump Game II](https://oj.leetcode.com/problems/jump-game-ii/)| [Java](./src/main/java/indi/ours/algorithm/leetcode/algorithms/_45.java)|Hard| Array Greedy|O(n)|O(1) |Q55|
317317
|44|[Wildcard Matching](https://oj.leetcode.com/problems/wildcard-matching/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/wildcardMatching/wildcardMatching)|Hard|
318318
|43|[Multiply Strings](https://oj.leetcode.com/problems/multiply-strings/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/multiplyStrings/multiplyStrings)|Medium|
319319
|42|[Trapping Rain Water](https://oj.leetcode.com/problems/trapping-rain-water/)| [Java](src/main/java/indi/ours/algorithm/leetcode/algorithms/_1.java/trappingRainWater/trappingRainWater)|Hard|

‎LeetCode/src/main/java/indi/ours/algorithm/leetcode/algorithms/_45.java

Lines changed: 165 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,165 @@
1+
package indi.ours.algorithm.leetcode.algorithms;
2+
3+
/**
4+
* @author wangheng
5+
* @create 2018-12-27 下午1:59
6+
* @desc
7+
* Given an array of non-negative integers, you are initially positioned at the first index of the array.
8+
*
9+
* Each element in the array represents your maximum jump length at that position.
10+
*
11+
* Your goal is to reach the last index in the minimum number of jumps.
12+
*
13+
* Example:
14+
*
15+
* Input: [2,3,1,1,4]
16+
* Output: 2
17+
* Explanation: The minimum number of jumps to reach the last index is 2.
18+
* Jump 1 step from index 0 to 1, then 3 steps to the last index.
19+
* Note:
20+
*
21+
* You can assume that you can always reach the last index.
22+
*
23+
* 给定一个非负整数数组，你最初位于数组的第一个位置。
24+
*
25+
* 数组中的每个元素代表你在该位置可以跳跃的最大长度。
26+
*
27+
* 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
28+
*
29+
* 示例:
30+
*
31+
* 输入: [2,3,1,1,4]
32+
* 输出: 2
33+
* 解释: 跳到最后一个位置的最小跳跃数是 2。
34+
* 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
35+
* 说明:
36+
*
37+
* 假设你总是可以到达数组的最后一个位置。
38+
*
39+
*
40+
**/
41+
public class _45 {
42+
43+
/**
44+
*
45+
* 后来 讨论区看了一下贪心算法
46+
*
47+
* @param nums
48+
* @return
49+
*/
50+
public int jump(int[] nums) {
51+
// If nums.length < 2, means that we do not
52+
// need to move at all.
53+
if (nums == null || nums.length < 2) {
54+
return 0;
55+
}
56+
57+
// First set up current region, which is
58+
// from 0 to nums[0].
59+
int l = 0;
60+
int r = nums[0];
61+
// Since the length of nums is greater than
62+
// 1, we need at least 1 step.
63+
int step = 1;
64+
65+
// We go through all elements in the region.
66+
while (l <= r) {
67+
68+
// If the right of current region is greater
69+
// than nums.length - 1, that means we are done.
70+
if (r >= nums.length - 1) {
71+
return step;
72+
}
73+
74+
// We should know how far can we reach in current
75+
// region.
76+
int max = Integer.MIN_VALUE;
77+
for (; l <= r; l++) {
78+
max = Math.max(max, l + nums[l]);
79+
}
80+
81+
// If we can reach far more in this round, we update
82+
// the boundary of current region, and also add a step.
83+
if (max > r) {
84+
l = r;
85+
r = max;
86+
step++;
87+
}
88+
}
89+
90+
// We can not finish the job.
91+
return -1;
92+
93+
}
94+
95+
96+
/**
97+
* BFS 求解
98+
* @param nums
99+
* @return
100+
*/
101+
public int jump(int[] nums) {
102+
//只有一个元素
103+
if (nums.length <= 1) return 0;
104+
//当前可以到达的最大元素
105+
int curMax = 0; // to mark the last element in a level
106+
//层数 和 起始点
107+
int level = 0, i = 0;
108+
109+
while (i <= curMax) {
110+
111+
int furthest = curMax; // to mark the last element in the next level
112+
// 求出 相对的 可以到达的最远的点
113+
// nums[i]+i 的问题可以算出 该点 i 可以到达的最远点
114+
//主要是 curMax记录的问题
115+
//如何让level 自增
116+
117+
for (; i <= curMax; i++) {
118+
furthest = Math.max(furthest, nums[i] + i);
119+
if (furthest >= nums.length - 1) return level + 1;
120+
}
121+
level++;
122+
curMax = furthest;
123+
}
124+
return -1; // if i < curMax, i can't move forward anymore (the last element in the array can't be reached)
125+
}
126+
127+
128+
/**
129+
* 将 Q55 题目的问题 拿来 加以变化
130+
* @param nums
131+
* @return
132+
*/
133+
134+
public int jump(int [] nums){
135+
//只有一个元素
136+
if (nums.length <= 1) return 0;
137+
int level = 0;
138+
139+
// 设计 起点 和 终点
140+
int i = 0, j= 0;
141+
142+
// 当i < j 时 说明还有路可通
143+
//如果i>j 说明 该 数组 不可跳跃
144+
//比如 【3，2，1，0，0，1】
145+
while (i<=j){
146+
147+
//每一次 j 获取最大值的过程
148+
//level 都要自增一次
149+
int max = Integer.MIN_VALUE;
150+
while (i<=j){
151+
//记录 该 层 可以到达的最远点
152+
max = Math.max(max,i + nums[i++]);
153+
if(max >=nums.length -1) return level ++ ;
154+
}
155+
//将最大值 赋值给 j ；
156+
//并 将 层数 ++ ；
157+
j = max ;
158+
level++ ;
159+
160+
}
161+
162+
return -1 ;
163+
}
164+
}
165+

‎LeetCode/src/main/java/indi/ours/algorithm/leetcode/algorithms/_55.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package indi.ours.algorithm.leetcode.algorithms;
2+
3+
/**
4+
* @author wangheng
5+
* @create 2018-12-27 下午3:58
6+
* @desc
7+
*
8+
* Given an array of non-negative integers, you are initially positioned at the first index of the array.
9+
*
10+
* Each eleme 100B nt in the array represents your maximum jump length at that position.
11+
*
12+
* Determine if you are able to reach the last index.
13+
*
14+
* Example 1:
15+
*
16+
* Input: [2,3,1,1,4]
17+
* Output: true
18+
* Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
19+
* Example 2:
20+
*
21+
* Input: [3,2,1,0,4]
22+
* Output: false
23+
* Explanation: You will always arrive at index 3 no matter what. Its maximum
24+
* jump length is 0, which makes it impossible to reach the last index.
25+
*
26+
*
27+
*
28+
*
29+
**/
30+
public class _55 {
31+
32+
/**
33+
*
34+
* @param nums
35+
* @return
36+
*/
37+
public boolean canJump(int[] nums) {
38+
39+
if(nums==null || nums.length ==0)return false ;
40+
int i =0 ,j = 0 ;
41+
while(i <=j && j <nums.length) {
42+
//计算j 可以到达的最大位置
43+
//i + nums[i] 当前i的 位置 和 i 可以到达的位置 同时i++
44+
//这样计算了每个i 上的最大位置
45+
j =Math.max(j,i+nums[i++]);
46+
}
47+
48+
return j >nums.length-1 ;
49+
50+
51+
}
52+
53+
54+
/**
55+
* 我想了一下 试试 用动态规划的方法
56+
* 看看能不能解决问题
57+
* @param nums
58+
* @return
59+
*/
60+
public boolean canJump(int[] nums) {
61+
if(nums==null || nums.length ==0)return false ;
62+
int maxindex = nums.length-1 ;
63+
nums[maxindex] = -1 ;
64+
//不停地修改 数组 为 -1 即是可达 为 -2 即为 不可达
65+
for(int i = maxindex-1 ; i >=0 ;i--){
66+
//如果直接可达
67+
int tmpmax = i +nums[i];
68+
if(tmpmax >maxindex){
69+
nums[i] = -1 ;
70+
71+
}else {
72+
for (int j = i; j <= tmpmax; j++) {
73+
if (nums[j] == -1) {
74+
nums[i] = -1;
75+
}
76+
}
77+
}
78+
}
79+
return nums[0] == -1 ;
80+
81+
}
82+
83+
84+
}

0 commit comments

Comments
 (0)
0