Bài 45 Leetcode: Jump Game II

Đề bài:

Bạn được cho một mảng số nguyên nums có độ dài n và được đánh chỉ mục từ 0. Ban đầu, bạn đứng tại vị trí nums[0].

Mỗi phần tử nums[i] đại diện cho độ dài tối đa của một bước nhảy tiến từ chỉ mục i. Nghĩa là, nếu bạn đang ở nums[i], bạn có thể nhảy đến bất kỳ nums[i + j] nào thoả mãn:

  • 0 <= j <= nums[i] và
  • i + j < n

Trả về số bước nhảy tối thiểu để đạt được nums[n – 1]. Các bộ test được tạo ra sao cho bạn có thể đến được nums[n – 1].

Ví dụ 1:

Input: nums = [2,3,1,1,4]
Output: 2
Giải thích: Số bước nhảy tối thiểu để đến được chỉ mục cuối cùng là 2. Nhảy 1 bước từ chỉ mục 0 đến 1, sau đó nhảy 3 bước để đến chỉ mục cuối cùng.

Ví dụ 2:

Input: nums = [2,3,0,1,4]
Output: 2

Ràng buộc:

  • 1 <= độ dài của nums <= 10^4
  • 0 <= nums[i] <= 1000
  • Đảm bảo rằng bạn có thể đến được nums[n – 1].

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

class Solution {
 public:
  int jump(vector<int>& nums) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    // Implicit BFS
    for (int i = 0; i < nums.size() - 1; ++i) {
      farthest = max(farthest, i + nums[i]);
      if (farthest >= nums.size() - 1) {
        ++ans;
        break;
      }
      if (i == end) {    // Visited all the items on the current level.
        ++ans;           // Increment the level.
        end = farthest;  // Make the queue size for the next level.
      }
    }

    return ans;
  }
};

Đây là một giải thuật giải bài toán tìm số bước nhảy tối thiểu để đến vị trí cuối cùng trong mảng `nums`. Dưới đây là giải thích chi tiết về giải thuật:

1. Khởi tạo biến `ans` (số bước nhảy tối thiểu) bằng 0.

2. Khởi tạo biến `end` (vị trí kết thúc của một cấp độ) bằng 0.

3. Khởi tạo biến `farthest` (vị trí xa nhất mà có thể đạt được từ vị trí hiện tại) bằng 0.

4. Tiến hành duyệt qua mảng `nums` từ đầu đến trước vị trí cuối cùng (nums.size() – 1).

5. Tại mỗi vị trí `i`:

– Cập nhật `farthest` bằng giá trị lớn nhất giữa `farthest` hiện tại và `i + nums[i]`. Điều này đại diện cho việc tìm vị trí xa nhất mà có thể đạt được từ vị trí hiện tại.

– Kiểm tra nếu `farthest` lớn hơn hoặc bằng vị trí cuối cùng của mảng `nums` – 1. Nếu điều kiện này đúng, tức là đã đến được vị trí cuối cùng, ta tăng `ans` lên 1 và thoát khỏi vòng lặp.

– Kiểm tra nếu `i` bằng `end`. Điều này đại diện cho việc đã duyệt qua tất cả các phần tử trên cùng một cấp độ. Khi xảy ra điều này, ta tăng `ans` lên 1 (để chuyển sang cấp độ tiếp theo) và cập nhật `end` bằng `farthest` (để xác định kích thước hàng đợi cho cấp độ tiếp theo).

6. Trả về giá trị của `ans` là số bước nhảy tối thiểu để đến vị trí cuối cùng.

Giải thuật này sử dụng một phương pháp tương tự BFS (Tìm kiếm theo chiều rộng ngầm định) để tìm số bước nhảy tối thiểu. Bằng cách duyệt qua từng phần tử và cập nhật `farthest`, ta tìm được vị trí xa nhất mà có thể đạt được từ mỗi vị trí hiện tại. Khi duyệt hết các phần tử trên cùng một cấp độ, ta tăng `ans` lên 1 và chuyển sang cấp độ tiếp theo.

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

class Solution {
  public int jump(int[] nums) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    // Start an implicit BFS.
    for (int i = 0; i < nums.length - 1; ++i) {
      farthest = Math.max(farthest, i + nums[i]);
      if (farthest >= nums.length - 1) {
        ++ans;
        break;
      }
      if (i == end) {   // Visited all the items on the current level.
        ++ans;          // Increment the level.
        end = farthest; // Make the queue size for the next level.
      }
    }

    return ans;
  }
}

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

class Solution:
  def jump(self, nums: List[int]) -> int:
    ans = 0
    end = 0
    farthest = 0

    # Start an implicit BFS.
    for i in range(len(nums) - 1):
      farthest = max(farthest, i + nums[i])
      if farthest >= len(nums) - 1:
        ans += 1
        break
      if i == end:      # Visited all the items on the current level.
        ans += 1        # Increment the level.
        end = farthest  # Make the queue size for the next level.

    return ans

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.