LeetCodeカップル手をつないでHERODINGのLeetCodeの道
N組のカップルは、連続して並んでいる2 N席に座り、相手の手を引っ張りたい.カップルごとに肩を並べて座ることができるように、座席を交換する回数を最小限に抑えます.1回の交換で任意の2人を選択し、立ち上がって席を交換させることができます.
人と座席は0から2 N-1の整数で表され、カップルは順番に番号付けされ、1対目は(0,1)、2対目は(2,3)、このようにして最後のペアは(2 N-2,2 N-1)である.
これらのカップルの初期席row[i]は、最初にi番目の席に座った人によって決まる.
例1:
入力:row=[0,2,1,3]出力:1解釈:row[1]とrow[2]の位置を交換するだけでよい.
例2:
入力:row=[3,2,0,1]出力:0解釈:席を交換する必要はなく、すべてのカップルが手をつないでいることができます.
説明:
大みそかにまたバレンタインデーに会って、LeetCodeの毎日の1題も負けないで、困難な難易度の問題は各位のカップルを外出させたくないようです.本題に戻ると、最低交換席数を統計するには、欲張りな考え方で解決し、偶数桁のカップルを固定し、奇数桁のカップルが期待している位置にいるかどうかを確定し、いる場合はスキップ(++2)し、いない場合は、所在地を見つけて現在の奇数位置と交換すればよい.コードは以下の通りである.
人と座席は0から2 N-1の整数で表され、カップルは順番に番号付けされ、1対目は(0,1)、2対目は(2,3)、このようにして最後のペアは(2 N-2,2 N-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 。
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/couples-holding-hands著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.大みそかにまたバレンタインデーに会って、LeetCodeの毎日の1題も負けないで、困難な難易度の問題は各位のカップルを外出させたくないようです.本題に戻ると、最低交換席数を統計するには、欲張りな考え方で解決し、偶数桁のカップルを固定し、奇数桁のカップルが期待している位置にいるかどうかを確定し、いる場合はスキップ(++2)し、いない場合は、所在地を見つけて現在の奇数位置と交換すればよい.コードは以下の通りである.
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int count = 0;
for(int i = 0; i < row.size(); i += 2) {
int object = find(row[i]);
//
if(row[i + 1] != object) {
int index = findIndex(object, row);
int temp = row[i + 1];
row[i + 1] = object;
row[index] = temp;
count ++;
}
}
return count;
}
//
int find(int n) {
if(n % 2 == 0) {
return n + 1;
} else {
return n - 1;
}
}
//
int findIndex(int n, vector<int>& row) {
for(int i = 0; i < row.size(); i ++) {
if(row[i] == n) {
return i;
}
}
return -1;
}
};
/* :heroding
:https://leetcode-cn.com/problems/couples-holding-hands/solution/czui-xiang-xi-ti-jie-by-heroding-5341/
: (LeetCode)
。 , 。*/