Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
private:
    vector<int> f, rank;
    struct Edge {
        int v, u, w;
        bool operator < (const Edge& e) const {
            return w < e.w;
        }
    };
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    bool _union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        else if (rank[fx] > rank[fy])
            swap(fx, fy);
        rank[fy] += rank[fx];
        f[fx] = fy;
        return true;
    }
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 1) return 0;
        vector<Edge> graph;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                graph.push_back({i, j, 
                    abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
        f = vector<int>(n, 0);
        rank = vector<int>(n, 1);
        for (int i = 0; i < n; ++i)
            f[i] = i;
        sort(graph.begin(), graph.end());
        int ans = 0;
        for (Edge& e : graph)
            if (_union(e.v, e.u)) {
                ans += e.w;
                if (--n == 1)
                    return ans;
            }
        return -1;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        UF uf = new UF();
        Map<String, Integer> emailToId = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int id = 0;
        for (List<String> account : accounts) {
            String name = "";
            for (String email : account) {
                if (name.length() == 0) {
                    name = email;
                    continue;
                }
                emailToName.put(email, name);
                if (!emailToId.containsKey(email))
                    emailToId.put(email, id++);
                uf.union(emailToId.get(account.get(1)), emailToId.get(email));
            }
        }
        Map<Integer, List<String>> ans = new HashMap<>();
        for (String email : emailToName.keySet()) {
            int i = uf.find(emailToId.get(email));
            ans.computeIfAbsent(i, k -> new ArrayList<>()).add(email);
        }
        for (List<String> l : ans.values()) {
            Collections.sort(l);
            l.add(0, emailToName.get(l.get(0)));
        }
        return new ArrayList(ans.values());
    }
}
class UF {
    private int[] f;
    public UF() {
        f = new int[10001];
        for (int i = 0; i <= 10000; i++)
            f[i] = i;
    }
    public int find(int i) {
        int j = i;
        while (i != f[i])
            i = f[i];
        while (f[j] != i) {
            int next = f[j];
            f[j] = i;
            j = next;
        }
        return i;
    }
    public void union(int i, int j) {
        f[find(j)] = find(i);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Set<String>> graph = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                graph.computeIfAbsent(account.get(i), k -> new HashSet<>());
                emailToName.put(account.get(i), name);
                if (i == 1) continue;
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
        Set<String> visited = new HashSet<>();
        List<List<String>> ans = new LinkedList<>();
        for (String email : emailToName.keySet()) {
            List<String> list = new LinkedList<>();
            if (visited.add(email)) {
                dfs(graph, email, visited, list);
                Collections.sort(list);
                list.add(0, emailToName.get(email));
                ans.add(list);
            }
        }
        return ans;
    }
    private void dfs(Map<String, Set<String>> graph, String email, Set<String> visited, List<String> list) {
        list.add(email);
        for (String next : graph.get(email))
            if (visited.add(next))
                dfs(graph, next, visited, list);
    }
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        const int n = coordinates.size();
        if (n == 2) return true;
        if (coordinates[1][0] == coordinates[0][0]) {
            int x = coordinates[0][0];
            for (int i = 2; i < n; ++i)
                if (coordinates[i][0] != x)
                    return false;
        } else {
            double k = (coordinates[1][1] - coordinates[0][1]) / (1.0 * coordinates[1][0] - coordinates[0][0]);
            double b = coordinates[0][1] - k * coordinates[0][0];
            for (int i = 2; i < n; ++i)
                if ((k * coordinates[i][0] + b) != coordinates[i][1])
                    return false;
        }
        return true;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class UnionFind {
private:
    vector<int> f, sz;
public:
    UnionFind(int n): f(n), sz(n) {
        for (int i = 0; i < n; ++i) {
            f[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (sz[fx] > sz[fy])
                swap(fx, fy);
            sz[fy] += sz[fx];
            f[fx] = fy;
        }
    }
    int size(int x) {
        return sz[find(x)];
    }
};
class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        const int R = grid.size(), C = grid[0].size();
        UnionFind uf(R * C + 1);
        vector<vector<int>> status = grid;
        for (int i = 0; i < hits.size(); ++i)
            status[hits[i][0]][hits[i][1]] = 0;
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                if (status[r][c] == 1) {
                    if (r == 0)
                        uf.merge(R * C, r * C + c);
                    if (r > 0 && status[r - 1][c] == 1)
                        uf.merge(r * C + c, (r - 1) * C + c);
                    if (c > 0 && status[r][c - 1] == 1)
                        uf.merge(r * C + c, r * C + c - 1);
                }
        const vector<int> dirs{-1, 0, 1, 0, -1};
        vector<int> ans(hits.size(), 0);
        for (int i = hits.size() - 1; i >= 0; --i) {
            int r = hits[i][0], c = hits[i][1];
            if (grid[r][c] == 0) continue;
            int prev = uf.size(R * C);
            if (r == 0)
                uf.merge(c, R * C);
            for (int j = 0; j < 4; ++j) {
                int nr = r + dirs[j], nc = c + dirs[j + 1];
                if (nr < 0 || nr >= R || nc < 0 || nc>= C || status[nr][nc] != 1) continue;
                uf.merge(r * C + c, nr * C + nc);
            }
            int curr = uf.size(R * C);
            ans[i] = max(0, curr - prev - 1);
            status[r][c] = 1;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        const int n = stones.size();
        vector<vector<int>> edges(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1]))
                    edges[i].emplace_back(j);
        vector<bool> visited(n);
        function<void(int)> dfs = [&](int x) {
            visited[x] = true;
            for (const int y : edges[x])
                if (!visited[y])
                    dfs(y);
        };
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(i);
            }
        return n - cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        const int n = stones.size();
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < n; ++i) {
            m[stones[i][0]].emplace_back(i);
            m[stones[i][1] + 10000].emplace_back(i);
        }
        vector<vector<int>> edges(n);
        for (const auto& [_, vec] : m) {
            const int k = vec.size();
            for (int i = 1; i < k; ++i) {
                edges[vec[i - 1]].emplace_back(vec[i]);
                edges[vec[i]].emplace_back(vec[i - 1]);
            }
        }
        vector<bool> visited(n);
        function<void(int)> dfs = [&](int x) {
            visited[x] = true;
            for (const int y : edges[x])
                if (!visited[y])
                    dfs(y);
        };
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(i);
            }
        return n - cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class DisjointSetUnion {
private:
    unordered_map<int, int> f, rank;
public:
    int find(int x) {
        if (f.find(x) == f.end()) {
            f[x] = x;
            rank[x] = 1;
        }
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (rank[fx] > rank[fy])
                swap(fx, fy);
            rank[fy] += rank[fx];
            f[fx] = fy;
        }
    }
    int numberOfConnectedComponent() {
        int cnt = 0;
        for (auto &[x, fa] : f)
            if (x == fa)
                ++cnt;
        return cnt;
    }
};
class Solution {
public:
    int removeStones(vector<vector<int>> &stones) {
        const int n = stones.size();
        DisjointSetUnion dsu;
        for (int i = 0; i < n; ++i)
            dsu.unionSet(stones[i][0], stones[i][1] + 10000);
        return n - dsu.numberOfConnectedComponent();
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> ans;
        int mask = 0;
        for (const int i : A) {
            mask = ((mask << 1) + i) % 5;
            ans.emplace_back(mask == 0);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        const int n = edges.size();
        vector<int> f(n + 1, 0);
        vector<int> size(n + 1, 0);
        auto find = [&](int i) {
            int j = i;
            while (i != f[i]) i = f[i];
            while (j != i) {
                int next = f[j];
                f[j] = i;
                j = next;
            }
            return j;
        };
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (!f[u]) f[u] = u;
            if (!f[v]) f[v] = v;
            int uf = find(u), vf = find(v);
            if (uf == vf) return edge;
            if (size[vf] > size[uf])
                swap(vf, uf);
            f[vf] = uf;
            size[uf] += size[vf];
        }
        return {};
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);
        int leftId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1)
                group[i] = leftId++;
            groupItem[group[i]].emplace_back(i);
        }

        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);
        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    ++itemDegree[i];
                    itemGraph[item].emplace_back(i);   
                } else {
                    ++groupDegree[curGroupId];
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        vector<int> id;
        for (int i = 0; i < n + m; ++i)
            id.emplace_back(i);
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0)
            return vector<int>{};

        vector<int> ans;
        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) continue;    
            vector<int> itemTopSort = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (itemTopSort.size() == 0) return vector<int>{};
            ans.insert(ans.end(), itemTopSort.begin(), itemTopSort.end());
        }
        return ans;
    }
private:
    vector<int> topSort(vector<int>& indeg, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> q;
        for (auto& item: items)
            if (indeg[item] == 0)
                q.push(item);
        vector<int> ans;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ans.emplace_back(u);
            for (auto& v: graph[u])
                if (--indeg[v] == 0)
                    q.push(v);
        }
        return ans.size() == items.size() ? ans : vector<int>{};
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses, vector<int>());
        vector<int> indeg(numCourses, 0);
        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i)
            if (indeg[i] == 0)
                q.push(i);
        vector<int> ans;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ans.push_back(u);
            for (int v: edges[u])
                if (--indeg[v] == 0)
                    q.push(v);
        }
        return ans.size() == numCourses ? ans : vector<int>();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites)
            edges[info[1]].push_back(info[0]);
        for (int i = 0; i < numCourses && valid; ++i)
            if (visited[i] == 0)
                dfs(i);
        if (!valid) return vector<int>();
        reverse(ans.begin(), ans.end());
        return ans;
    }
private:
    vector<vector<int>> edges;
    vector<int> visited;
    vector<int> ans;
    bool valid = true;
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u])
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) return;
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        visited[u] = 2;
        ans.push_back(u);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses, vector<int>());
        vector<int> indeg(numCourses, 0);
        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i)
            if (indeg[i] == 0)
                q.push(i);
        while (!q.empty()) {
            --numCourses;
            int u = q.front(); q.pop();
            for (int v : edges[u])
                if (--indeg[v] == 0)
                    q.push(v);
        }
        return numCourses == 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites)
            edges[info[1]].push_back(info[0]);
        for (int i = 0; i < numCourses && valid; ++i)
            if (visited[i] == 0)
                dfs(i);
        return valid;
    }
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u])
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) return;
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        visited[u] = 2;
    }
};
0%