Viiisit [LeetCode] - 55. Jump Game

keep learning, keep coding!

Problem - Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

翻譯蒟蒻

從給定的整數陣列 nums 的第一個索引出發，按照每個索引處的數字所表示的最大跳躍長度，最終達到陣列的最後一個索引。每個陣列元素代表你在該位置可以跳躍的最大步數。

• Example 1:

  Input: nums = [2,3,1,1,4]
  Output: true
  Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

• Example 2:

  Input: nums = [3,2,1,0,4]
  Output: false
  Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

---

Solution - JavaScript

Solution 1:

/**
 * @param {number[]} nums
 * @return {boolean}
 */

var canJump = function(nums) {
  // 初始化最大可達距離為 0
  let maxLength = 0; 

  for (let i = 0; i < nums.length; i++) {
    if (i > maxLength) {
      // 如果當前索引 i 超過了最大可達距離 maxLength，
      // 表示無法到達這個索引，直接返回 false
      return false;
    }

    // 更新最大可達距離，取當前最大可達距離和（i + nums[i]）的較大值，確保在每一步中，選擇最大的可達距離。
    maxLength = Math.max(maxLength, i + nums[i]);

    if (maxLength >= nums.length - 1) {
      // 如果目前的最大可達距離已經超過或等於最後一個索引，則可以到達最後一個索引
      return true;
    }
  }

  // 如果結束後都沒有返回 true，表示無法到達最後一個索引，返回 false
  return false;
};

Solution 1 是使用貪婪演算法（greedy algorithm），從左至右遍歷陣列，
維護一個變數 maxLength 表示當前所能達到的最遠距離。

貪婪演算法（greedy algorithm），是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，從而希望導致結果是最好或最佳的演算法。

• 過程：
  • 對於每一個位置 i，檢查是否超過了當前的最大可達距離 maxLength。
  • 如果超過，表示無法到達這個索引，直接返回 false。
  • 否則，更新 maxLength 為 i + nums[i] 的較大值，確保每一步都選擇最大的可達距離。

Solution 2:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  // 初始化最後一個能夠到達終點的位置為最後一個索引
  let lastPosition = nums.length - 1; 
  
  for (let i = nums.length - 2; i >= 0 ; i--) {
    if (i + nums[i] >= lastPosition) {
      // 如果當前位置 i 能夠到達或超過最後一個能夠到達的位置 lastPosition，
      // 則更新 lastPosition 為當前位置 i
      lastPosition = i;
    }
  }

  // 最終檢查 lastPosition 是否為 0，如果是，表示能夠到達最後一個索引
  return lastPosition === 0;
};

Solution 2 是使用反向的迴圈，從最後一個索引開始，維護一個變數 lastPosition 表示最後一個能夠到達終點的位置。

• 過程：
  • 從最後一個索引開始，對於每一個位置 i，檢查 i + nums[i] 是否大於等於 lastPosition。
  • 如果是，表示當前位置 i 可以跳到最後一個位置，則將 lastPosition 更新為 i。

Solution - Ruby

Solution 1:

def can_jump(nums)
  max_length = 0
  nums.each_with_index do |num, i|
    return false if i > max_length

    max_length = [max_length, i + nums[i]].max

    return true if max_length >= nums.length - 1
  end

  false
end

Solution 2:

def can_jump(nums)
  last_position = nums.length - 1
  
  # 從倒數第二個數字開始到 0 為止
  (nums.length - 2).downto(0) do |i|
    last_position = i if i + nums[i] >= last_position
  end

  last_position == 0
end

LeetCode 傳送門 - Jump Game