C++의 점프 게임 IV

arr이라는 정수 배열이 있다고 가정합니다. 우리는 처음에 인덱스 0에 있습니다. 한 단계에서 인덱스 i에서 i + x로 이동할 수 있습니다. 여기서 i + x =0. j 여기서:arr[i] 및 arr[j]는 동일하고 i 및 j는 동일하지 않습니다. 여기서 n은 배열의 크기입니다. 배열의 마지막 인덱스에 도달하려면 최소 단계 수를 찾아야 합니다.

따라서 입력이 다음과 같으면

C++의 점프 게임 IV

그러면 출력은 3이 됩니다. 인덱스 0에서 4로, 3에서 9로 세 번 점프해야 합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 맵 정의
n :=arr의 크기
initialize i :=0의 경우, i
- m[arr[i]]
  끝에 i 삽입
m[arr[i]]
끝에 i 삽입
방문에 0 삽입
하나의 대기열 정의 q
초기화 lvl :=0의 경우 q가 비어 있지 않으면 업데이트(lvl을 1만큼 증가), do-
- sz :=q의 크기
- sz가 0이 아닌 동안 각 반복에서 sz를 1 do −
  줄입니다.
  - curr :=q의 첫 번째 요소
  - q에서 요소 삭제
  - curr이 n - 1과 같으면
    - 레벨을 반환
  - 나는 :=커
  - i - 1>=0이고 i - 1이 방문되지 않은 경우 -
    - q에 i - 1 삽입
    - 방문에 i - 1 삽입
  - i + 1
    - q에 i + 1 삽입
    - 방문에 i + 1 삽입
  - j 초기화의 경우:=0, j
    - (m[arr[curr], j])가 방문되지 않은 경우 -
      - m[arr[curr], j]를 q
        에 삽입
      - m[arr[curr], j]를 방문
        에 삽입
  - arr[curr]이 m에 없으면 -
    - m에서 arr[curr] 삭제
반환 -1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

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