[数据结构与算法]力扣765——情侣牵手（贪心+BFS）

解题思路

空间换时间

可以发现，每对情侣谁左谁右，旁边是谁，都没关系，只要这俩是一对且在一格就行；
因为要求全坐好，因为首尾不相连，下标0只能和下标1配对，这就相当于一格为两个偶奇下标；
首先遍历每一格，把情侣先剔除，以及在一起了不必调整；将当前不是情侣但坐一起的存集合里；
之后随机将一对未配对的入队，进行BFS，如果找到目标，进行交换；
如果交换后的那组正好也配对，就再找一组新的入队；
如果交换后未配对，那将这两个未配对但坐一起的入队；

因为相互次序无关，可以通过反证法证明这样贪心的正确性

代码

class Solution {
public:
    bool iscouple(int a, int b) {
        if(a % 2 == 0 && a + 1 == b) return true;
        if(b % 2 == 0 && b + 1 == a) return true;
        return false;
    }
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int ans = 0;
        set<pair<int, int>> notcouple;
        for(int i = 0; i < n; i+=2) {
            int a = row[i], b = row[i+1];
            if(!iscouple(a, b))  notcouple.insert({a, b}); 
        }
        if(notcouple.size() == 0) return ans;
        queue<pair<int, int>> q;
        auto x = *notcouple.begin();
        q.push(x);        
        while(!q.empty()) {
            auto [a1, a2] = q.front(); q.pop();
            notcouple.erase({a1, a2});
            ans++;
            int target = a1 % 2 ? a1 - 1: a1 + 1;
            int flag = 0;   //是否需要再找一个加进队列
            for(auto [b1, b2] : notcouple) {
                if(b1 == -1) continue;
                if(b1 == target) {  //a1,b1配对
                    if(iscouple(a2, b2)) {  //正好a2,b2配对
                        notcouple.erase({b1, b2}); flag = 1;
                    }
                    else {
                        notcouple.erase({b1, b2});
                        notcouple.insert({a2, b2});
                        q.push({a2, b2});
                    }
                    break;
                }
                if(b2 == target) {
                    if(iscouple(a2, b1)) {
                        notcouple.erase({b1, b2}); flag = 1;
                    }
                    else {
                        notcouple.erase({b1, b2});
                        notcouple.insert({a2, b1});
                        q.push({a2, b1});
                    }
                    break;
                }
            }
            if(flag) {
                if(notcouple.empty()) break;
                else q.push(*notcouple.begin());
            }
        }
        return ans;
    }
};