publicbooleancanJump(int[] nums){ int len = nums.length; boolean[] visited = newboolean[len]; visited[0] = true; for (int i = 0; i < len; i++) { int steps = nums[i]; if (visited[i] && steps > 0) { for (int j = 1; j <= steps && i + j < len; j++) { visited[i + j] = true; } } }
return visited[len - 1]; }
Analysis
Time Complexity: O(n2)
Space Complexity: O(n)
Greedy
Jump to the farest postion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
publicbooleancanJump(int[] nums){ int len = nums.length; int maxIdx = 0; for (int i = 0; i < len; i++) { int steps = nums[i]; if (maxIdx >= i) { maxIdx = Math.max(maxIdx, i + steps); if (maxIdx >= len - 1) { returntrue; } } }
publicstaticintjump_dp(int[] nums){ int len = nums.length; if (len <= 1) { return0; }
int[] dp = newint[len]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int minStep = Integer.MAX_VALUE; for (int i = 0; i < len; i++) { int num = nums[i]; for (int j = 1; j <= num && i + j < len; j++) { dp[i + j] = Math.min(dp[i + j], dp[i] + 1); if (i + j >= len - 1) { minStep = Math.min(minStep, dp[i] + 1); return minStep; } } }
return minStep; }
Analysis
Time Complexity: O(n2)
Space Complexity: O(n)
Greedy
1 2 3 4 5 6 7 8 9 10 11 12 13 14
publicintjump(int[] nums){ int maxPosition = 0; int end = 0; int steps = 0; for (int i = 0; i < nums.length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } }
return steps; }
Think reverse, from destination to origin position.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
publicintjump(int[] nums){ int ans = 0; int position = nums.length - 1; while (position > 0) { for (int i = 0; i < position; i++) { if (i + nums[i] >= position) { ans++; position = i; break; } } }
publicstaticbooleancanJump(int[] nums){ int len = nums.length; int maxIdx = 0; for (int i = 0; i < len; i++) { int steps = nums[i]; if (maxIdx >= i) { maxIdx = Math.max(maxIdx, i + steps); if (maxIdx >= len - 1) { returntrue; } } }