leetcode 765カップルが手をつないで

一.原題の説明
N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.
The people and seats are represented by an integer from 0 to 2N-1 , the couples are numbered in order, the first couple being (0, 1) , the second couple being (2, 3) , and so on with the last couple being (2N-2, 2N-1) .
The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.
Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

len(row) is even and in the range of [4, 60] .

row is guaranteed to be a permutation of 0...len(row)-1 .

二.中国語の説明
N組のカップルは、連続して並んでいる2 N席に座り、相手の手を引っ張りたい.カップルごとに肩を並べて座ることができるように、座席を交換する回数を最小限に抑えます.1回の交換で任意の2人を選択し、立ち上がって席を交換させることができます.
人と座席は0から2N-1の整数で表され、カップルは順番に番号が付けられ、第1対は(0, 1)、第2対は(2, 3)で、このようにして、最後のペアは(2N-2, 2N-1)である.
これらのカップルの初期座席row[i]は、最初にi番目の席に座った人によって決定される.
例1:

  : row = [0, 2, 1, 3]
  : 1
  :        row[1] row[2]     。

例2:

  : row = [3, 2, 0, 1]
  : 0
  :       ，              。

説明:

len(row)は偶数であり、数値は[4, 60]の範囲内である.

は、rowがシーケンス0...len(row)-1の全配列であることを保証することができる.

三.問題を解く構想.
1.この問題では、まずデータを観察してみると、各カップルに対応する数値差は1であり、各カップルは隣接しなければならず、前後を問わず(すなわち、1組のカップル0、1の配列は1、0であってもよく、2人がそれぞれ対応する奇数位と偶数位であれば)
2.理解を助けるために、以下の例を挙げる
0位
1位
2位
3位
人対応番号
1
0
2
3
人対応番号
2
3
0
1
上の表は要件を満たすデータです
以下はテストデータ
グループ
0位
1位
2位
3位
第1グループ
0
2
1
3
第2グループ
3
2
0
1
3.次は解題です
(1)まず偶数位を固定して判断する(もちろんカップルごとに奇数位しか判断できない)、上記の表のテストデータを例にとると、0位と2位しか判断できない.
(2)第1グループ0位の判断では,まず人間0,そのカップルの値は1,第2グループ0位の判断では3,対応するカップル2となるので,以下の関係式を抽象化することができる.

j=cp[i]%2==0?cp[i]+1:cp[i]-1;

このうちjはcp[i]対応のカップルであり、cp[i]が偶数の場合、その対応するカップルはcp[i]+1に等しく、cp[i]が奇数の場合、その対応するカップルはcp[i]-1に等しい
(3)その後,上記の関係式に基づいてループを行い,cp[i]対応するカップルを見つけて交換する.このときコードは以下のようになる.

for(int i=0;i<cp_len;i+=2)
        {
            int j;
            j=cp[i]%2==0?cp[i]+1:cp[i]-1;
            if(cp[i+1]!=j)
            {
                count0++;
                for(int m=i+2;m<cp_len;m++)
                {
                    if(cp[m]==j)//  j 
                    {
                        swap(cp[m],cp[i+1]);//  

                   break;
                }
            }
        }

    }

iは我々が検出した偶数ビットであり、jはcp[i]に対応するカップル値であり、cp[i+1]!=jの場合,i+2ビットからjを探し,見つけたら交換し,このサイクルを繰り返すと正解が得られる.
(4)完全なソースコードは以下の通りである.

#include
using namespace std;

class couple{
public:

int match_couple(int* cp,int lenth)
{
    count0=0;

    cp_len=lenth;

    for(int i=0;i<cp_len;i+=2)
    {
        int j;
        j=cp[i]%2==0?cp[i]+1:cp[i]-1;
        if(cp[i+1]!=j)
        {
            count0++;
          //  cout<
            for(int m=i+2;m<cp_len;m++)
            {
                if(cp[m]==j)
                {
                    swap(cp[m],cp[i+1]);

                    break;
                }
            }
        }

    }

    return count0;
}

private:
    int count0;
    int cp_len;



};

void swap(int* a,int* b)
{
    *a=*a+*b;
    *b=*a-*b;
    *a=*a-*b;
}

int main()
{
    couple couples;

int a[]={0,2,1,3},lenth=0,swap_count=0;
lenth=sizeof(a)/sizeof(a[0]);
swap_count=couples.match_couple(a,lenth);
cout<<swap_count;

return 0;

}