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
-
C++でゲームIVをジャンプする
arrという整数の配列があるとします。最初はインデックス0にいます。1つのステップで、インデックスiからi + xにジャンプできます。ここで、i +x =0。jここで:arr[i]とarr[j]は同じであり、iとjは同じではありません。ここで、nは配列のサイズです。配列の最後のインデックスに到達するための最小ステップ数を見つける必要があります。 したがって、入力が次のような場合、 その場合、出力は3になります。インデックス0から4、3から9への3つのジャンプが必要です。 これを解決するには、次の手順に従います- 1つのマップを定義するm n:=arrのサイズ 初期
-
C++で奇数と偶数のノードを含むすべてのレベルを出力します
この問題では、ツリーが与えられます。そして、偶数のノードと奇数のノードを含むすべてのレベルを印刷する必要があります。 概念をよりよく理解するために例を見てみましょう 出力- Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2 説明 −第1レベルには1つの要素(奇数)、第2レベルには2つの要素(偶数)、第3レベルには3つの要素(奇数)、第4レベルには1つの要素(偶数)が含まれます。 さて、この問題を解決するために。各レベルでノードの数を見つけ、それに応じて偶数-奇数レベルを出力す