C++での奇数ジャンプ

これで、インデックス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になります。これは、最後に到達できる場所から2つの場所のインデックス3と4があるためです。

これを解決するには、次の手順に従います-

• ret：=1

• n：=Aのサイズ

• サイズnの配列nextGreaterEqualを定義します。これを-1で埋めます

• サイズnの配列nextSmallerEqualを定義します。これを-1で埋めます

• 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

• サイズnx2の2D配列vを1つ定義し、これをfalseで埋めます

• v [n-1、0] =v [n-1、1] =true

• 初期化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]がゼロ以外の場合、-

    • （retを1増やします）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

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

出力

2