二刷
Version #2 Greedy
Exit early when step end reaches the last index
Time O(N)
Space O(1)
Runtime: 1 ms, faster than 99.93% of Java online submissions for Jump Game II.
Memory Usage: 43.1 MB, less than 84.43% of Java online submissions for Jump Game II.
class Solution {
public int jump(int[] nums) {
// furthest defines the furthest index that we can reach
// Every time the furthest is updated, we need to make an extra jump
int furthest = 0;
int stepEnd = 0; // The furthest that we can reach within current number of steps
int step = 0;
for (int i = 0; i < nums.length; i++) {
if (i > furthest) {
return -1;
}
if (i > stepEnd) {
step++;
stepEnd = furthest;
}
furthest = Math.max(furthest, i + nums[i]);
if (stepEnd >= nums.length - 1) {
return step;
}
}
return -1;
}
}
一刷
Version #2 Greedy
Time O(N)
Space O(1)
Runtime: 1 ms, faster than 99.90% of Java online submissions for Jump Game II.
Memory Usage: 49.9 MB, less than 23.57% of Java online submissions for Jump Game II.
class Solution {
public int jump(int[] nums) {
int steps = 0;
int furthest = 0;
int currEnd = 0;
for (int i = 0; i < nums.length - 1; i++) {
// With a steps, we can reach the range
// [start, end]
// Update the next furthest index until we reach end
furthest = Math.max(furthest, nums[i] + i);
if (i == currEnd) {
steps++;
currEnd = furthest;
}
}
return steps;
}
}
23.54 %
class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int step = 0;
Set<Integer> visited = new HashSet<>();
visited.add(0);
int len = nums.length;
Queue<Integer> que = new LinkedList<>();
que.offer(0);
while (!que.isEmpty()) {
int size = que.size();
// [2,3,1,1,4] curr = 0 next = 1 i = 1, 2
step++;
while (size-- > 0) {
int curr = que.poll();
int next = curr + nums[curr];
for (int i = 0; i < nums[curr]; i++) {
if (next >= len - 1) {
return step;
}
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
next--;
}
}
}
return -1;
}
}
No comments:
Post a Comment