C++의 홀수 짝수 점프

배열 A가 있다고 가정합니다. 일부 시작 인덱스에서 일련의 점프를 만들 수 있습니다. 연속으로 위치(1, 3, 5, ...) 점프하는 것을 홀수 점프라고 하고, 시리즈에서 위치(2, 4, 6, ...)로 점프하는 것을 짝수 점프라고 합니다.

이제 인덱스 i에서 다음과 같은 방식으로 인덱스 j(i

홀수 점프 동안 A[i] <=A[j] 및 A[j]가 가능한 가장 작은 값이 되도록 인덱스 j로 점프할 수 있습니다. 이러한 인덱스 j가 여러 개 있는 경우 가장 작은 인덱스 j로만 이동할 수 있습니다.
짝수 번호 점프 중에 A[i]>=A[j] 및 A[j]가 가능한 가장 큰 값이 되도록 인덱스 j로 점프할 수 있습니다. 이러한 인덱스 j가 여러 개 있는 경우 가장 작은 인덱스 j로만 이동할 수 있습니다.
일부 인덱스 i의 경우 법적 점프가 없는 경우일 수 있습니다.

이제 시작 인덱스는 해당 인덱스에서 시작하여 몇 번 점프하여 배열의 끝에 도달할 수 있을 때 good이라고 합니다.

좋은 시작 인덱스의 수를 찾아야 합니다.

따라서 입력이 [10,13,12,14,15]와 같으면 출력은 2가 됩니다. 끝에 도달할 수 있는 두 자리 인덱스 3과 4가 있기 때문입니다.

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

렛 :=1
n :=A의 크기
크기가 n인 배열 nextGreaterEqual을 정의합니다. 이를 -1로 채웁니다.
크기가 n인 배열 nextSmallerEqual을 정의합니다. 이를 -1로 채웁니다.
하나의 맵 st 정의
초기화 i :=n - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
- if :=값이 A[i]보다 크지 않은 키-값 쌍
- nextGreaterEqual[i] :=(it)이 마지막 요소가 아니면 그 값, 그렇지 않으면 -1
- st의 마지막 요소와 같지 않고 첫 번째 요소가 A[i]와 같으면 -
  - (1씩 증가)
- nextSmallerEqual[i] :=(it)이 첫 번째 요소가 아니면 이전 값, 그렇지 않으면 -1
- st[A[i]] :=i
크기가 n x 2인 하나의 2D 배열 v를 정의하고 이를 false로 채웁니다.
v[n - 1, 0] =v[n - 1, 1] =참
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
- nextGreaterEqual[i]가 -1과 같지 않으면 -
  - v[i, 1] :=v[nextGreaterEqual[i], 0]
- nextSmallerEqual[i]가 -1과 같지 않으면 -
  - v[i, 0] :=v[nextSmallerEqual[i], 1]
- v[i, 1]이 0이 아니면 -
  - (ret 1 증가)
리턴 렛

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int oddEvenJumps(vector<int>& A){
      int ret = 1;
      int n = A.size();
      vector<int> nextGreaterEqual(n, -1);
      vector<int> nextSmallerEqual(n, -1);
      map<int, int> st;
      for (int i = n - 1; i >= 0; i--) {
         map<int, int>::iterator it = st.lower_bound(A[i]);
         nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
         if (it != st.end() && it->first == A[i])
         it++;
         nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
         : -1;
         st[A[i]] = i;
      }
      vector<vector<bool> > v(n, vector<bool>(2, false));
      v[n - 1][0] = v[n - 1][1] = true;
      for (int i = n - 2; i >= 0; i--) {
         if (nextGreaterEqual[i] != -1) {
            v[i][1] = v[nextGreaterEqual[i]][0];
         }
         if (nextSmallerEqual[i] != -1) {
            v[i][0] = v[nextSmallerEqual[i]][1];
         }
         if (v[i][1])
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,13,12,14,15};
   cout << (ob.oddEvenJumps(v));
}

입력

{10,13,12,14,15}