Jump Game 的三种思路 - leetcode 55. Jump Game

Jump Game 是一道有意思的题目。题意很简单，给你一个数组，数组的每个元素表示你能前进的最大步数，最开始时你在第一个元素所在的位置，之后你可以前进，问能不能到达最后一个元素位置。

比如：

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

一种走法是 0 - 2 - 3 - 4，还有一种走法是 0 - 1 - 4

O(n ^ 2) 解法

一个很显然，几乎不用动脑的解法。

设置一个布尔数组f，f[0] === true 表示 index === 0 这个位置能够到达，模拟每个位置的前进，最后判断 f[lastIndex] 的值。

/** * @param {number[]} nums * @return {boolean} */var canJump = function(nums) {  var f = [];  f[0] = true;  nums.forEach(function(item, index, array) {    if (f[index]) {      var tmp = Math.min(array.length - 1, index + item)      for (var i = index + 1; i <= tmp; i++)        f[i] = true;    }  });  return f[nums.length - 1] ? false : true;};

但是返回了无情的TLE，给出了一组TLE的数据，数组长度达到了25000，也就是复杂度达到了O(25000 ^ 2)，虽然leetcode数据普遍很弱，但是这组TLE也是让我心服口服。

解法1，跪...

O(nlogn) 解法

方法总比困难多，联想到了树状数组中的染色问题。

我们可以把jump的过程看成是染色，还是从左到右枚举位置，比如枚举到 index=0 位置时，nums[0]=5，也就是说从 index=0 的位置一直可以走到 index=5 的位置，那么我们可以把1~5这一段进行染色。当枚举到 index=1 时，如何判断能不能走到这一步呢？只需求该点被染色的次数，如果大于0，那么就是能到达，然后从该点向后继续染色，最后判断最后一点有没有被染色即可。复杂度 O(nlongn)。

/** * @param {number[]} nums * @return {boolean} */var sum, n;function lowbit(x) {  return x & (-x);}function update(index, val) {  while (index) {    sum[index] += val;    index -= lowbit(index);  }}function getAns(index) {  var ans = 0;  while (index <= n) {    ans += sum[index];    index += lowbit(index);  }  return ans;}var canJump = function(nums) {  sum = [];  sum[1] = 1;  n = nums.reduce(function(pre, item, index) {    return Math.max(pre, item + index + 1);  }, 0);  for (var i = 2; i <= n; i++)    sum[i] = 0;  for (var i = 0, len = nums.length; i < len; i++) {    var isPainted = getAns(i + 1); // 是否被染色    if (!isPainted) continue;    update(i + 1 + nums[i], 1);    update(i, -1);  }  return Boolean(getAns(len));};

O(n) 解法

用树状数组显然大材小用了，树状数组可以求得被染色的次数，但是本题只需要判断是否被染色即可；而且本题每次染色都是一次。

进一步思考，我们枚举每一位时都在判断是否被染色过（从而决定是否能够到达该点且能否继续往前走），假设在某一瞬间，index=m 的位置已经被染色了，那么 index=n (n<=m) 的位置肯定已经被染色过了，我们维护一个最右边被染色的点，如果当前枚举点在该点的左侧，那么当前点已经被染色，否则即可停止遍历（因为右边的点再也不可能被染色到了）。

/** * @param {number[]} nums * @return {boolean} */var canJump = function(nums) {  var rightMost = 1;  for (var i = 0, len = nums.length; i < len; i++) {    if (rightMost < i + 1) break;    rightMost = Math.max(rightMost, i + 1 + nums[i]);  }  return rightMost >= len;};