刷题前唠嗑

LeetCode? 启动！！！

好好好，这么玩是吧，双十一出道情侣牵手

题目：情侣牵手

题目链接：765. 情侣牵手

题目描述

代码与解题思路

func minSwapsCouples(row []int) (ans int) {
    n := len(row)
    index := make([]int, n)
    for i := 0; i < n; i++ {
        index[row[i]] = i // 存下标
    }
    for i := 0; i < n-1; i+=2 {
        a := row[i]
        b := a^1 // 无论 a 位置是奇数还是偶数, a^1 的结果求出的都是 a 的情侣 b 的值
        if row[i+1] != b {
            // src 是 a 旁边位置的人的下标, tar 是 a 的情侣 b 的坐标(之前存在下标数组中了)
            src, tar := i+1, index[b]
            // 这两步是将 src 和 tar 在下标数组的下标位置交换
            index[row[tar]] = src
            index[row[src]] = tar
            swap(&row[tar], &row[src]) // 交换情侣的位置
            ans++
        }
    }
    return ans
}

func swap(a, b *int) {
    *a, *b = *b, *a
}

这道题虽然是 hard，但是做起来没有这么 hard，我的代码思路如下：

这里先盗用一下 LeetCode 官解的图：

首先我们要理解上面这张图的情况，最少交换次数=情侣对数-1

1. 创建一个下标数组，用来存每个人的下标
2. a 代表当前位置的人，b 代表 a 对应的情侣
3. 如果 a 和 b 不是一对情侣，那就通过下标数组找到 a 对应的情侣，并将他交换到 a 的旁边；这样子遍历一遍 row 数组，就能将 row 中所有的情侣都组好队（因为遍历了一遍，对于每一个不是情侣的组合都进行了寻找和交换的操作）
4. 每次进行寻找和交换就让 ans++ 计数即可

题解说这是贪心（那就当他是贪心吧~）因为我其实不太会贪心，所以看不出来。

偷看大佬题解

题解说可以用并查集来做，实际上我没有学过图论，所以。。。我也不会并查集啦，那就当没看见吧~

结语

今天就当是扩展思路涨见识了~