刷题分享11_28

刷题分享

1.（力扣15）这是一道求三数之和的问题，如果使用哈希表的方法了话，十分难实现去重的操作，所以我们可以考虑将问题拆分，即先用一个for循环遍历数组，在每一层遍历内部（相当于确定下来第一个数），使用双指针的方法，这样利用指针＋＋或－－的操作，可以很方便的实现去重的操作。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0){
                return res;
            }
            int left=i+1;
            int right=nums.size()-1;
            if(i>0&&nums[i-1]==nums[i]){
                continue;
            }
            while(left<right){
                vector<int>tem;
                if(nums[i]+nums[left]+nums[right]==0){
                    tem.push_back(nums[i]);
                    tem.push_back(nums[left]);
                    tem.push_back(nums[right]);
                    left++;right--;
                    res.push_back(tem);
                while(right>left&&nums[right+1]==nums[right]){
                    right--;
                }
                while(right>left&&nums[left-1]==nums[left]){
                    left++;
                }
                }else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }else{
                    left++;;
                }
            }
        }return res;
    }
};

2.（力扣765）这是一道情侣牵手的问题，通过 其下标与对于情侣编号的关系，可以联想到使用并查集。因为并查集有三大基本操作：1.build，即创建一个并查集。2.find，即寻找给定元素的代表元素。 3.union，即将所给数字所在的两个集合合并（合并其实就是将两个集合的代表元素变成同一个）。此题还有一个核心在于想明白对于一个集合，如果它里面包含了K对情侣中的人，那么该集合必须要交换K－1次（相当于每交换一次，可以成全一对情侣，最后一次交换可以将最后两对情侣一起成全，所以是K－1次），res其实就是各个集合交换次数之和。想明白上面几点之后，其实本题就是在并查集的基本操作里加入一个size变量，用来记录当前集合的个数，最后返回n/2-size即可

class Solution {
public:

    #define len 31
    int father[len]={0};
    int size=0;

    void build(int m){
        for(int i=0;i<m;i++){
            father[i]=i;
        }
        size=m;
    }

    int find(int num){
        if(num!=father[num]){
            father[num]=find(father[num]);
        }
        return father[num];
    }

       void uni(int x,int y){
        int findx=find(x);
        int findy=find(y);
        if(findx!=findy){
            father[findx]=find(y);
            size--;
        }
    }

    int minSwapsCouples(vector<int>& row) {
        int n=row.size();
        build(n/2);
        for(int i=0;i<n;i+=2){
            uni(row[i]/2,row[i+1]/2);
        }
        return n/2-size;
    }
};