Bài 55 Leetcode: Jump Game

Đề bài:

Bạn được cho một mảng số nguyên `nums`. Ban đầu, bạn đang đứng tại vị trí đầu tiên của mảng và mỗi phần tử trong mảng đại diện cho số bước nhảy tối đa mà bạn có thể thực hiện từ vị trí đó.

Trả về true nếu bạn có thể đến được vị trí cuối cùng của mảng, và trả về false nếu không thể đến được.

Ví dụ 1:

Input: nums = [2,3,1,1,4]
Output: true
Giải thích: Nhảy 1 bước từ vị trí 0 đến vị trí 1, sau đó nhảy 3 bước để đến vị trí cuối cùng.

Ví dụ 2:

Input: nums = [3,2,1,0,4]
Output: false
Giải thích: Bất kể như thế nào, bạn luôn đến được vị trí có chỉ số 3. Tuy nhiên, độ dài nhảy tối đa của nó là 0, điều này làm cho việc đến được vị trí cuối cùng là không thể.

Ràng buộc:

• 1 <= độ dài của mảng nums <= 10^4
• 0 <= nums[i] <= 10^5

Giải thích thuật toán bằng C ++

class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int i = 0;

    for (int reach = 0; i < nums.size() && i <= reach; ++i)
      reach = max(reach, i + nums[i]);

    return i == nums.size();
  }
};

Đây là một đoạn mã C++ để kiểm tra xem có thể nhảy đến vị trí cuối cùng của một mảng số nguyên hay không.

Hàm `canJump` nhận đầu vào là một vector `nums` chứa các số nguyên, trong đó mỗi số đại diện cho số bước nhảy tối đa từ mỗi vị trí.

Biến `i` được khởi tạo là 0 và đại diện cho vị trí hiện tại của người nhảy.

Trong vòng lặp `for`, biến `reach` được khởi tạo là 0 và đại diện cho vị trí xa nhất mà người nhảy có thể đạt được từ các vị trí trước đó. Vòng lặp này sẽ tiếp tục cho đến khi `i` vượt quá kích thước của mảng hoặc `i` vượt quá vị trí xa nhất `reach`.

Trong mỗi vòng lặp, ta cập nhật `reach` bằng cách so sánh giá trị hiện tại của `reach` và `i + nums[i]`, nghĩa là vị trí xa nhất mà người nhảy có thể đạt được từ vị trí hiện tại `i`.

Sau khi kết thúc vòng lặp, ta kiểm tra xem giá trị của `i` có bằng kích thước của mảng không. Nếu `i` bằng kích thước của mảng, điều này có nghĩa là ta đã nhảy đến vị trí cuối cùng của mảng và hàm trả về true. Ngược lại, nếu `i` khác kích thước của mảng, điều này có nghĩa là ta không thể nhảy đến vị trí cuối cùng và hàm trả về false.

Đây là một cách tiếp cận để kiểm tra xem có thể nhảy đến vị trí cuối cùng của mảng bằng cách duyệt qua các vị trí và cập nhật vị trí xa nhất mà người nhảy có thể đạt được từ các vị trí trước đó.

Giải thích thuật toán bằng Java

class Solution {
  public boolean canJump(int[] nums) {
    int i = 0;

    for (int reach = 0; i < nums.length && i <= reach; ++i)
      reach = Math.max(reach, i + nums[i]);

    return i == nums.length;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def canJump(self, nums: List[int]) -> bool:
    i = 0
    reach = 0

    while i < len(nums) and i <= reach:
      reach = max(reach, i + nums[i])
      i += 1

    return i == len(nums)