?LeetCode刷題實戰(zhàn)55：跳躍游戲
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?跳躍游戲，我們先來看題面：
https://leetcode-cn.com/problems/jump-game/
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
題意
樣例
示例?1:
輸入: [2,3,1,1,4]
輸出:
true
解釋: 我們可以先跳
1?步，從位置
0?到達(dá) 位置
1, 然后再從位置
1?跳
3?步到達(dá)最后一個位置。
示例?2:
輸入: [3,2,1,0,4]
輸出:
false
解釋: 無論怎樣，你總會到達(dá)索引為
3?的位置。但該位置的最大跳躍長度是
0?， 所以你永遠(yuǎn)不可能到達(dá)最后一個位置。
解題
public?class?Solution?{
??
??int?steps;
?
??public?int?jump(int[] nums)?{
????????int?n = nums.length;
????????steps = n -
1;
????????
????????jump(nums,
0,
0);
????????
????????return?steps;
????}
??
??private?void?jump(int[] nums, int?index, int?tempSteps)?{
????if(index >= nums.length -
1) {
??????if(index == nums.length -
1) {
????????steps = Math.min(steps, tempSteps);
??????}
??????return;
????}
????for?(int?i =
1; i <= nums[index]; i++) {
??????jump(nums, index + i, tempSteps +
1);
????}
??}
}
public?class?Solution?{
?
??public?int?jump(int[] nums)?{
????????int?n = nums.length;
????????if(n == 1) {
??????????return?0;
????????}
????????int[][] steps = new?int[n][n];
????????for?(int?i = 0; i < n; i++) {
??????for?(int?j = 0; j < n; j++) {
????????steps[i][j] = n - 1;
??????}
????}
????????for?(int?i = 0; i < n; i++) {
??????steps[i][i] = 0;
????}
????????for?(int?i = 0; i >= 1?- n; i--) {
??????for?(int?j = 0; j < n + i; j++) {
????????if(nums[j] + j >= j - i) {
??????????steps[j][j - i] = 1;
????????}else?{
??????????for?(int?k = 1; k <= nums[j]; k++) {
????????????steps[j][j - i] = Math.min(steps[j][j - i], 1?+ steps[j + k][j - i]);
??????????}
????????}
??????}
????}
????????return?steps[0][n - 1];
????}
}
public?class?Solution?{
??
??public?int?jump(int[] nums)?{
????????int?n = nums.length;
????????int?steps = 0;
????????int?index = 0;
????????while(index < n - 1) {
??????????steps++;
??????????int[] lengths = new?int[nums[index]];
??????????if(index + nums[index] >= n - 1) {
????????????break;
??????????}
??????????for?(int?i = index + 1; i <= index + nums[index]; i++) {
????????lengths[i - index - 1] = i + nums[i];
??????}
??????????int?max = 0;
??????????for?(int?i = 0; i < lengths.length; i++) {
????????if(lengths[i] > lengths[max]) {
??????????max = i;
????????}
??????}
??????????index = max + index + 1;
????????}
????????return?steps;
????}
}
上期推文：