Leetcode 765 情侣牵手

题目描述

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (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
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

解题思路

这题是一个贪心题，但是怎么贪和模拟的过程需要好好注意一下，这种需要交换位置的题我们可以使用一个map来存储值在数组中的下标。我们从前往后遍历数组，遇到已经可以牵手的情侣直接continue。然后碰到第一对不能牵手的情侣开始处理，我们找到不符合要求的那个数，计算和他能牵手的人的值，然后通过值和之前建立的map找到这个人在数组中的下标，然后把这个不符合要求的数换到这个下标的左边或者右边（这个根据条件简单判断即可，得保证这一对情侣在正确的位置上，比如下标如果为1，2就是不正确的位置，要是(0,1),(2,3)这种才是符合要求的）。替换以后，被替换的那个数我们拿出来继续执行之前的操作，直到第一次拿出来的那个不符合要求的数被替换掉了，这样我们就可以继续遍历之后的元素了。需要注意的是，我们每一步这样求出来的次数是比正确值多一的，为什么呢？因为比如我们需要交换第1个和第3个元素，在我们这个模拟中要执行两步操作才能使交换成立，但是实际我们交换这两个人就行了，一步就可以搞定。

AC代码

class Solution {
public:int minSwapsCouples(vector<int>& row) {int num = row.size();int p = 0;map<int, int>M;//M储存值为val元素的下标for (int i = 0; i < num; i++)M[row[i]] = i;int sum = 0;//int p = 0;while (p < num) {if (row[p] / 2 == row[p + 1] / 2) {p += 2;continue;}else {int n = row[p], m, c, index;do {if (n % 2) m = n - 1;else m = n + 1;index = M[m];if (index % 2)index--;else index++;c = row[index];row[index] = n;n = c;sum++;} while (index != p);sum--;}}return sum;
}
};

小结

模拟操作真的急需要多练，码力真的太烂了每次模拟边界条件都要调半天。