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
46
47
48
49
50
51
52
53
54
55
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    UF(int _n): n(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y])
                swap(x, y);
            f[y] = x;
            size[x] += size[y];
        }
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size();
        vector<tuple<int, int, int>> edges;
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c) {
                int idx = r * C + c;
                if (r < R - 1) {
                    edges.emplace_back(idx, idx + C, abs(heights[r + 1][c] - heights[r][c]));
                }
                if (c < C - 1) {
                    edges.emplace_back(idx, idx + 1, abs(heights[r][c + 1] - heights[r][c]));
                }
            }
        sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, w1] = e1;
            auto&& [x2, y2, w2] = e2;
            return w1 < w2;
        });
        UF uf(R * C);
        int lastIdx = R * C - 1;
        for (const auto [x, y, w] : edges) {
            uf._union(x, y);
            if (uf.connected(0, lastIdx))
                return w;
        }
        return 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
30
31
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size();
        int left = 0, right = 999999, ans = 0, lastIdx = R * C - 1, dirs[] = {1, 0, -1, 0, 1};
        while (left <= right) {
            int mid = (left + right) / 2;
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            vector<bool> seen(R * C);
            seen[0] = true;
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                for (int i = 0; i < 4;) {
                    int nr = r + dirs[i], nc = c + dirs[++i];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C || seen[nr * C + nc] 
                        || abs(heights[nr][nc] - heights[r][c]) > mid) continue;
                    q.emplace(nr, nc);
                    seen[nr * C + nc] = true;
                }
            }
            if (seen[lastIdx]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};
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
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size(), dirs[] = {1, 0, -1, 0, 1};
        auto tupleCmp = [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, d1] = e1;
            auto&& [x2, y2, d2] = e2;
            return d1 > d2;
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(tupleCmp)> q(tupleCmp);
        q.emplace(0, 0, 0);
        vector<int> dist(R * C, INT_MAX);
        dist[0] = 0;
        vector<bool> seen(R * C);
        while (!q.empty()) {
            auto [r, c, d] = q.top(); q.pop();
            int idx = r * C + c;
            if (seen[idx]) continue;
            if (r == R - 1 && c == C - 1) break;
            seen[idx] = true;
            for (int i = 0; i < 4;) {
                int nr = r + dirs[i], nc = c + dirs[++i];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                int nd = max(d, abs(heights[r][c] - heights[nr][nc]));
                if (nd >= dist[nr * C + nc]) continue;
                dist[nr * C + nc] = nd;
                q.emplace(nr, nc, dist[nr * C + nc]);
            }
        }
        return dist[R * C - 1];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int currSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * currSum + nums[i] == sum)
                return i;
            currSum += nums[i];
        }
        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
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    int setCount; // count of current connected components
    UF(int _n): n(_n), setCount(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    bool _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        f[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
};
class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        UF ufa(n + 1), ufb(n + 1); // 0 as one dummy node
        int ans = 0;
        for (const auto& edge : edges)
            if (edge[0] == 3)
                if (!ufa._union(edge[1], edge[2]))
                    ++ans;
                else
                    ufb._union(edge[1], edge[2]);
        for (const auto& edge : edges)
            if (edge[0] == 1) {
                if (!ufa._union(edge[1], edge[2]))
                    ++ans;
            } else if (edge[0] == 2) {
                if (!ufb._union(edge[1], edge[2]))
                    ++ans;
            }
        if (ufa.setCount != 2 || ufb.setCount != 2) // 1 connected component and a dummy node
            return -1;
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<int> numCnt(100, 0);
        int ans = 0;
        for (const auto& d : dominoes) {
            int v = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
            ans += numCnt[v];
            ++numCnt[v];
        }
        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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class UF {
public:
    vector<int> f;
    vector<int> size;
    int setCount; // count of current connected components
    UF(int n): setCount(n), f(n), size(n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (size[fx] < size[fy])
                swap(fx, fy);
            f[fy] = fx;
            size[fx] += size[fy];
            --setCount;
        }
    }
};
class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        const int n = grid.size();
        UF uf(n * n * 4); // east 0, south 1, west 2, north 3
        for (int r = 0; r < n; ++r)
            for (int c = 0; c < n; ++c) {
                int idx = r * n + c;
                int easternIndex = idx * 4;
                if (r < n - 1) {
                    int bottom = idx + n;
                    uf._union(easternIndex + 1, bottom * 4 + 3);
                }
                if (c < n - 1) {
                    int right = idx + 1;
                    uf._union(easternIndex, right * 4 + 2);
                }
                if (grid[r][c] == '/') {
                    uf._union(easternIndex, easternIndex + 1);
                    uf._union(easternIndex + 2, easternIndex + 3);
                } else if (grid[r][c] == '\\') {
                    uf._union(easternIndex, easternIndex + 3);
                    uf._union(easternIndex + 1, easternIndex + 2);
                } else {
                    uf._union(easternIndex, easternIndex + 1);
                    uf._union(easternIndex + 1, easternIndex + 2);
                    uf._union(easternIndex + 2, easternIndex + 3);
                }
            }
        return uf.setCount;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 0, l = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (r > 0 && nums[r] <= nums[r - 1])
                l = r;
            ans = max(ans, r - l + 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
26
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<vector<int>> g(n);
        for (const auto& c : connections) {
            g[c[0]].push_back(c[1]);
            g[c[1]].push_back(c[0]);
        }
        vector<bool> seen(n, false);
        int cnt = 0;
        function<void(int)> dfs = [&](int cur) {
            for (int next : g[cur])
                if (!seen[next]) {
                    seen[next] = true;
                    dfs(next);
                };
        };
        for (int i = 0; i < n; ++i)
            if (!seen[i]) {
                ++cnt;
                dfs(i);
            }
        return cnt - 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<int> p(n);
        iota(begin(p), end(p), 0);
        function<int(int)> find = [&](int x) {
            return p[x] == x ? x : p[x] = find(p[x]);
        };
        for (const auto& c :connections)
            p[find(c[0])] = find(c[1]);
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (i == p[i])
                ++cnt;
        return cnt - 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
class Solution {
public:
    vector<int> addToArrayForm(vector<int> &A, int K) {
        const int n = A.size();
        vector<int> ans;
        for (int i = n - 1; i >= 0; --i) {
            int sum = A[i] + K % 10;
            K /= 10;
            if (sum >= 10) {
                K++;
                sum -= 10;
            }
            ans.push_back(sum);
        }
        for (; K > 0; K /= 10)
            ans.push_back(K % 10);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> addToArrayForm(vector<int> &A, int K) {
        const int n = A.size();
        vector<int> ans;
        for (int i = n - 1; i >= 0 || K > 0; --i, K /= 10) {
            if (i >= 0)
                K += A[i];
            ans.push_back(K % 10);
        }
        reverse(ans.begin(), ans.end());
        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
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
65
66
67
68
69
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    int setCount; // count of current connected components
    UF(int _n): n(_n), setCount(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    bool _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y]) {
            swap(x, y);
        }
        f[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    bool connected(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }
};
class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        const int m = edges.size();
        for (int i = 0; i < m; ++i)
            edges[i].push_back(i); // preserve index before sorting
        sort(edges.begin(), edges.end(), [](const auto& u, const auto& v) {
            return u[2] < v[2]; // sort by weight
        });
        UF uf_std(n);
        int value = 0; // weight of MST
        for (int i = 0; i < m; ++i)
            if (uf_std._union(edges[i][0], edges[i][1]))
                value += edges[i][2];
        vector<vector<int>> ans(2);
        for (int i = 0; i < m; ++i) {
            UF uf(n);
            int v = 0;
            for (int j = 0; j < m; ++j)
                if (i != j && uf._union(edges[j][0], edges[j][1])) // without the i-th edge
                    v += edges[j][2];
            if (uf.setCount != 1 // graph can't be conncted as a single component
                || (uf.setCount == 1 && v > value)) { // or can be a conncted component with larger weight
                ans[0].push_back(edges[i][3]); // critical edges
                continue;
            }
            uf = UF(n);
            uf._union(edges[i][0], edges[i][1]);
            v = edges[i][2];
            for (int j = 0; j < m; ++j)
                if (i != j && uf._union(edges[j][0], edges[j][1]))
                    v += edges[j][2];
            if (v == value)
                ans[1].push_back(edges[i][3]); // pseudo-critical edges
        }
        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
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int min1 = INT_MAX, min2 = INT_MAX;
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        for (const int num : nums) {
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
        }
        return max(min1 * min2 * max1, max1 * max2 * max3);
    }
};
0%