C++でのリバースペア
配列があると仮定します。この配列では、次の条件を満たす場合、1つのペア(A[i]とA[j])を重要な逆ペアと呼びます-
- if i
2 * nums [j]
重要なリバースペアの数を見つける必要があります。したがって、入力が[2,8,7,7,2]の場合、結果は3になります。
これを解決するには、次の手順に従います-
- ans:=0
- 関数merge()を定義します。これにより、配列a、low、mid、highが取得されます。
- k:=高-低+ 1
- サイズkのアレイ温度を定義します
- i:=低、j =中+1、k:=0
- 最初:=半ば+ 1
- i <=midの間、-
- を実行します
- 最初の<=が高く、a[最初の]* 2 を実行します。
- (最初に1ずつ増やします)
- 最初の<=が高く、a[最初の]* 2 を実行します。
- while(j <=high and a [j] <=a [i])、do −
- temp [k]:=a [j]
- (jを1増やします)
- (kを1増やします)
- ans:=ans + first-(mid + 1)
- temp [k]:=a [i]
- (iを1増やします)
- (kを1増やします)
- を実行します
- temp [k]:=a [j]
- (kを1増やします)
- (jを1増やします)
- a [i]:=temp [k]
- (kを1増やします)
- 戻る
理解を深めるために、次の実装を見てみましょう-
例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int ans = 0;
void merge(vector <int> &a, lli low, lli mid, lli high){
lli k = high - low + 1;
vector <lli> temp(k);
lli i = low, j = mid + 1;
k = 0;
lli first = mid + 1;
while(i <= mid){
while(first <= high && (lli)a[first] * 2 < (lli)a[i]) {
first++;
}
while(j <= high && a[j] <= a[i])
{
temp[k] = a[j];
j++;
k++;
}
ans += first - (mid + 1);
temp[k] = a[i];
i++;
k++;
}
while(j <= high){
temp[k] = a[j];
k++;
j++;
}
k = 0;
for(lli i = low; i <= high; i++){
a[i] = temp[k];
k++;
}
}
void calc(vector <int> &a, lli low, lli high){
if(low >= high)return;
lli mid = low + (high - low)/2;
calc(a, low, mid);
calc(a, mid + 1, high);
merge(a, low, mid, high);
}
lli solve(vector<int> &A) {
ans = 0;
lli n = A.size();
calc(A, 0, n - 1);
return ans;
}
int reversePairs(vector<int>& nums) {
return solve(nums);
}
};
main(){
Solution ob;
vector<int> v = {2,8,7,7,2};
cout << (ob.reversePairs(v));
} 入力
{2,8,7,7,2} 出力
3
-
C++STLのリスト逆関数
この記事では、C++でのlist::reverse()関数の動作、構文、および例について説明します。 STLのリストとは リストは、任意の場所で一定時間の挿入と削除を順番に実行できるデータ構造です。リストは、二重にリンクされたリストとして実装されます。リストを使用すると、連続しないメモリ割り当てが可能になります。リストは、配列、ベクトル、および両端キューよりも、コンテナー内の任意の位置で要素の挿入抽出と移動を実行します。リストでは、要素への直接アクセスは遅く、リストはforward_listに似ていますが、フォワードリストオブジェクトは単一のリンクリストであり、フォワードでのみ繰り返すことが
-
C++のリバースビット
符号なし数値xが1つあり、その2進表現(32ビット符号なし整数)を簡単に見つけることができるとします。私たちの仕事はビットを逆にすることです。したがって、バイナリ表現が00000000000000000000001001110100のような場合、反転されたビットは00101110010000000000000000000000になります。したがって、ビットを反転した後に実際の数値を返す必要があります これを解決するには、次の手順に従います- nが指定された数であると仮定します 答えましょう:=0 for i:=31から0: answer:=Answer OR(n AND i)、そして