leetcode 305 union find

图片.png

• 重点：

1. & 符号决定代码速度：
   for (auto &bb : dics)
   int find(vector<int>& end, int id)
2. continue 也是比正常if 快:
   if (x < 0 || x >= m || y < 0 || y >= n || end[cur_id] == -1)
   continue;
   or
   if (x >= 0 && x < m&& y >= 0 && y < n && end[cur_id] != -1)

这类题目考察核心 或者说影响运行速度核心就是find()函数是如何写的：

1. 快速的做法 不采用递归：

int findRoot(vector<int>& roots, int i) {//没有用递归
            while (roots[i] != i) {
                roots[i] = roots[roots[i]];
                i = roots[i];
            }
            return i;
        }

2. 我的递归，超级烂：

int find(vector<int>& end, int id) {
        if (end[id] == id)
            return id;
        return find(end, end[id]);
    }

• code

class Solution {
public:
    int find(vector<int>& roots, int i) {//没有用递归
            while (roots[i] != i) {
                roots[i] = roots[roots[i]];
                i = roots[i];
            }
            return i;
        }
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> end(m*n, -1);
        vector<vector<int>> dics = { {0,1},{1,0},{0,-1},{-1,0} };
        int cnt = 0;
        vector<int>ans;
        for (auto& aa : positions) {
            int id = n * aa.first + aa.second;
            if (end[id] == -1) {
                end[id] = id;
                cnt++;
            }
            for (auto &bb : dics) {
                int x = bb[0] + aa.first, y = bb[1] + aa.second, cur_id = x * n + y;
                //if (x >= 0 && x < m&& y >= 0 && y < n && end[cur_id] != -1) 
                if (x < 0 || x >= m || y < 0 || y >= n || end[cur_id] == -1) continue;
                {
                    int t1 = find(end, cur_id), t2 = find(end, id);
                    if (t1 != t2) {
                        cnt--;
                        end[t1] = t2;
                    }

                }
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};