Jump Game IV trong C ++

Giả sử chúng ta có một mảng các số nguyên được gọi là arr. Ban đầu chúng ta đang ở chỉ số 0. Trong một bước, chúng ta có thể nhảy từ chỉ số i sang i + x trong đó:i + x =0. j trong đó:arr [i] và arr [j] giống nhau và i và j không giống nhau. Ở đây n là kích thước của mảng. Chúng ta phải tìm số bước tối thiểu để đạt được chỉ mục cuối cùng của mảng.

Vì vậy, nếu đầu vào giống như,

thì đầu ra sẽ là 3, Chúng ta cần ba bước nhảy từ chỉ số 0 đến 4 thành 3 đến 9.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một bản đồ m
n:=kích thước của arr
để khởi tạo i:=0, khi i
- chèn i vào cuối m [arr [i]]
chèn i vào cuối m [arr [i]]
chèn 0 vào đã truy cập
Xác định một hàng đợi q
để khởi tạo lvl:=0, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), do−
- sz:=kích thước của q
- trong khi sz khác 0, giảm sz trong mỗi lần lặp đi 1 do -
  - curr:=phần tử đầu tiên của q
  - xóa phần tử khỏi q
  - nếu curr giống với n - 1 thì
    - trả về lvl
  - i:=curr
  - nếu tôi - 1> =0 và không phải tôi - 1 được truy cập, thì -
    - chèn i - 1 vào q
    - chèn i-1 vào đã truy cập
  - nếu tôi + 1
    - chèn i + 1 vào q
    - chèn i + 1 vào đã truy cập
  - để khởi tạo j:=0, khi j
    - nếu (m [arr [curr], j]) không được truy cập, thì -
      - chèn m [arr [curr], j] vào q
      - chèn m [arr [curr], j] vào đã truy cập
  - nếu arr [curr] không phải bằng m, thì -
    - xóa arr [curr] khỏi m
trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minJumps(vector<int>& arr) {
      map<int, vector<int> > m;
      int n = arr.size();
      for (int i = 0; i < n; i++) {
         m[arr[i]].push_back(i);
      }
      set<int> visited;
      visited.insert(0);
      queue<int> q;
      q.push(0);
      for (int lvl = 0; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            int curr = q.front();
            q.pop();
            if (curr == n - 1)
            return lvl;
            int i = curr;
            if (i - 1 >= 0 && !visited.count(i - 1)) {
               q.push(i - 1);
               visited.insert(i - 1);
            }
            if (i + 1 < n && !visited.count(i + 1)) {
               q.push(i + 1);
               visited.insert(i + 1);
            }
            for (int j = 0; j < m[arr[curr]].size(); j++) {
               if (!visited.count(m[arr[curr]][j])) {
                  q.push(m[arr[curr]][j]);
                  visited.insert(m[arr[curr]][j]);
               }
            }
            if (m.count(arr[curr])) {
               m.erase(arr[curr]);
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
   cout << (ob.minJumps(v));
}

Đầu vào

{20,-5,-5,25,20,5,5,5,1,25}

Jump Game IV trong C ++

Ví dụ

Đầu vào

Đầu ra