转载

leetcode面试准备: Jump Game

1 题目

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.

For example:

A = [2,3,1,1,4] , return true .

A = [3,2,1,0,4] , return false .

接口: public boolean canJump(int[] nums);

2 思路

从数字的0位置，开始往后挑，是否能够达到最后一个元素。

思路1：一维动态规划

状态 F[i] ，表示从第0层出发，走到 A[i] 时剩余的还能够走的最大步数。

F[i] < 0 ：已经无法往前走了，只能够走到 i - 1层。

方程： F[i] = max(f[i - 1], A[i - 1]) - 1， i > 0
初始状态： F[0] = 0 或者 F[0] = A[0]

复杂度: Time: O(n) ； Space: O(n)

思路2：贪心思想

用 maxCan 表示能够走到的最远的index，不断更新这个 全局最值 。所以，有 局部最值 。

局部最值: maxLocal = A[i] + i ，表示走到i层时，能够达到的最远的index。

复杂度: Time: O(n) ； Space: O(1)

3 代码

思路1

 public boolean canJump(int[] nums) {   int len = nums.length;   int[] f = new int[len];   f[0] = nums[0];   for (int i = 1; i < len; i++) {    f[i] = Math.max(f[i - 1], nums[i - 1]) - 1;    if (f[i] < 0)     return false;   }   return f[len - 1] >= 0 ? true : false;  }

思路2

 public boolean canJump2(int[] nums) {   int len = nums.length;   int maxCan = 0;   for (int i = 0; (i < len) && (i <= maxCan); i++) {    int maxLocal = nums[i] + i;    maxCan = maxCan > maxLocal ? maxCan : maxLocal;    if (maxCan >= len - 1) {     return true;    }   }   return false;  }