Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

heap O(logn)

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 MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) { // 3次调整
        left.push(num); // 先放到左边最大堆调整
        right.push(left.top()); left.pop(); // 再取左边最大堆最大的数放到右边最小堆调整
        if (left.size() < right.size()) { // 如果左边数少则取右边最小堆最小的数放到左边最大堆再调整，要始终保持左边最大堆的数不少于右边最小堆的数
            left.push(right.top()); right.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return left.size() > right.size() ? left.top() : (left.top() + right.top()) * 0.5;
    }

private:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
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
class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if (left.empty() && right.empty()) {
            median = num;
            left.push(num);
            return;
        }
        if (num < median) {
            if (left.size() > right.size()) {
                right.push(left.top());
                left.pop();
            }
            left.push(num);
        }
        else {
            if (right.size() > left.size()) {
                left.push(right.top());
                right.pop();
            }
            right.push(num);
        }
        if (left.size() > right.size())
            median = left.top();
        else if (right.size() > left.size())
            median = right.top();
        else
            median = (left.top() + right.top()) / 2.0;
    }

    // Returns the median of current data stream
    double findMedian() {
        return median;
    }

private:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;
    double median;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

Posted on Edited on In Disqus:
Symbols count in article: 347 Reading time ≈ 1 mins.

O(h) time O(1) space
跟160. Intersection of Two Linked Lists一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        auto a = p, b = q;
        while (a != b) {
            a = a ? a->parent : q;
            b = b ? b->parent : p;
        }
        return a;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

multiset/hashheap O(nlogk)
跟239. Sliding Window Maximum方法不一样，太smart了
讨论一下添加删除的四种情况即可，两个if都能cover

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        multiset<int> s(begin(nums), begin(nums) + k);
        auto m = next(begin(s), k / 2);
        vector<double> res;
        for (int i = k; i <= n; ++i) {
            res.push_back((k & 1) ? *m : (*prev(m) + double(*m)) * 0.5);
            if (i == n) break;
            s.insert(nums[i]);
            if (nums[i] < *m) { // 偶变奇则需要前移
                --m;
            }
            if (nums[i - k] <= *m) { // 如果要删除的数有可能是*m要提前对m作调整，否则删除以后m就spoil了
                ++m; // 奇变偶需要后移
            }
            s.erase(s.find(nums[i - k]));
        }
        return res;
    }
};
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
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) return {};
        int n = nums.size();
        multiset<int> max, min;
        for (int i = 0; i < k; ++i) {
            max.insert(nums[i]);
        }
        for (int i = 0; i < k / 2; ++i) {
            min.insert(*max.rbegin());
            max.erase(max.find(*max.rbegin())); // Remember this usage!
        }
        vector<double> res;
        for (int i = k; i < n; ++i) {
            if (max.size() == min.size()) {
                res.push_back(*max.rbegin() / 2.0 + *min.begin() / 2.0); // (a + b) / 2.0 could overflow!
            }
            else {
                res.push_back(*max.rbegin());
            }
            if (max.count(nums[i - k])) {
                max.erase(max.find(nums[i - k]));
                max.insert(nums[i]);
            }
            else {
                min.erase(min.find(nums[i - k]));
                min.insert(nums[i]);
            }
            if (!max.empty() && !min.empty() && *max.rbegin() > *min.begin()) {
                int tmp = *max.rbegin();
                max.erase(max.find(tmp));
                max.insert(*min.begin());
                min.erase(min.begin());
                min.insert(tmp);
            }
        }
        if (max.size() == min.size()) {
            res.push_back(*max.rbegin() / 2.0 + *min.begin() / 2.0);
        }
        else {
            res.push_back(*max.rbegin());
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 515 Reading time ≈ 1 mins.

直接覆盖 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for (int x : nums) {
            if (x != 0) {
                nums[j++] = x;
            }
        }
        fill(begin(nums) + j, end(nums), 0);
    }
};

swap O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        while (j < n) {
            while (i < n && nums[i] != 0) ++i;
            for (j = i + 1; j < n && nums[j] == 0; ++j);
            if (j >= n) break;
            swap(nums[i], nums[j]);
            ++i;
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 707 Reading time ≈ 1 mins.

O(n) time O(1) space
这道题的思路跟普通的reverse不一样！！
curr是固定的，永远指向初始的第m个结点，anchor也是固定的，永远是curr的前继结点
每次curr都是和它的succ交换，然后让next的下一个指向anchor的下一个结点，最后anchor的下一个指向那个succ结点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy_head(0), *anchor = &dummy_head;
        dummy_head.next = head;
        n -= m;
        while (--m > 0)
            anchor = anchor->next;
        auto curr = anchor->next;
        while (n-- > 0) {
            auto succ = curr->next;
            curr->next = succ->next;
            succ->next = anchor->next;
            anchor->next = succ;
        }
        return dummy_head.next;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

greedy O(n2) time
先排序，第一位降序，第二位升序，然后按照第二位插入排序
第一位小说明矮，靠后排，第二位大说明比他高的人多，靠后排
每次把一个人往前放，不会影响比他高的人的位置，不管是在他之前还是之后，之后影响比他矮且比他更靠后的人的位置，但是我们后面会处理他们，所以不用管他们
People are only counting (in their k-value) taller or equal-height others standing in front of them. So a smallest person is completely irrelevant for all taller ones. And of all smallest people, the one standing most in the back is even completely irrelevant for everybody else. Nobody is counting that person. So we can first arrange everybody else, ignoring that one person. And then just insert that person appropriately. Now note that while this person is irrelevant for everybody else, everybody else is relevant for this person - this person counts exactly everybody in front of them. So their count-value tells you exactly the index they must be standing.

So you can first solve the sub-problem with all but that one person and then just insert that person appropriately. And you can solve that sub-problem the same way, first solving the sub-sub-problem with all but the last-smallest person of the subproblem. And so on. The base case is when you have the sub-…-sub-problem of zero people. You’re then inserting the people in the reverse order, i.e., that overall last-smallest person in the very end and thus the first-tallest person in the very beginning. That’s what the above solution does, Sorting the people from the first-tallest to the last-smallest, and inserting them one by one as appropriate.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(begin(people), end(people), [](const vector<int> &lhs, const vector<int> &rhs) {
            return (lhs[0] == rhs[0]) ? (lhs[1] < rhs[1]) : (lhs[0] > rhs[0]);
        });
        vector<vector<int>> res;
        for (auto&& v : people) {
            res.insert(begin(res) + v[1], v);
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.8k Reading time ≈ 3 mins.

问一下target有没有长度限制！！
用这个 dp + memo O(N + N2 + … + NT) = O((N * (NT - 1) / (N - 1))即每一层有N次循环 一共T层 N是sticker个数 T是target长度
cache[target]是所求结果，cache[“”] = 0
对每个sticker统计字母频
对每一层的target统计字母频
用每一个sticker去尝试拼凑部分target，拼不上的部分组成新的target再递归
遍历所有的可能，不断更新最小值即可

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
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = stickers.size();
        vector<vector<int>> m(n, vector<int>(26));
        for (int i = 0; i < n; ++i) {
            for (char c : stickers[i]) {
                ++m[i][c - 'a'];
            }
        }
        int res = dfs(m, target);
        return res == INT_MAX ? -1 : res;
    }

    long dfs(const vector<vector<int>> &m, const string &target) {
        if (target.empty()) return 0;
        if (cache.count(target)) return cache[target];
        vector<int> mt(26);
        for (char c : target) {
            ++mt[c - 'a'];
        }
        int n = m.size();
        long res = INT_MAX; // 把当前结果初始化为INT_MAX
        for (int i = 0; i < n; ++i) {
            // if (m[i][target[0] - 'a'] == 0) continue; // 这个优化剪枝很神奇，可以避免潜在的对target完全没有贡献的sticker，暂时无法贡献的sticker等到其他sticker把部分target拼凑出来以后再贡献
            string s;
            for (int j = 0; j < 26; ++j) {
                if (mt[j] > m[i][j]) { // 这里大于或者大于等于无异，因为是要去掉当前sticker中可以拼成target的字母，所以如果sticker中的某个对应字母比target中的多，那么新组成的target就不需要添加该字母，所以只需要考虑sticker中对应字母不够拼成target的情况
                    s.append(mt[j] - m[i][j], 'a' + j);
                }
            }
            if (s == target) continue; // 如果没有之前那个优化，一定要判断新target和原target是否一样，避免重复递归
            res = min(res, dfs(m, s) + 1);
        }
        return cache[target] = res;
    }

    unordered_map<string, long> cache;
};

状态压缩dp O(2n*(S+n*s)) n是target长度 S是stickers所有字母个数 s是stickers的个数
target从一个字母都找不到匹配到所有字母都匹配上一共2n个状态

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
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        vector<int> f(1 << n, -1);
        f[0] = 0;
        for (int state = 0; state < (1 << n); ++state) {
            if (f[state] == -1) continue;
            for (const auto &s : stickers) {
                int now = state;
                int m[26] = {0};
                for (char c : s) {
                    ++m[c - 'a'];
                }
                for (int i = 0; i < n; ++i) {
                    if ((now >> i) & 1) continue;
                    if (m[target[i] - 'a']-- > 0) { // 用在哪个位置上无所谓，最后结果不影响
                        now |= (1 << i);
                    }
                }
                if (f[now] == -1 || f[now] > f[state] + 1) {
                    f[now] = f[state] + 1;
                }
            }
        }
        return f.back();
    }
};

状态压缩dp O(2n*n*S) n是target长度 S是stickers所有字母个数
target从一个字母都找不到匹配到所有字母都匹配上一共2n个状态

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
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        vector<int> f(1 << n, -1);
        f[0] = 0;
        for (int state = 0; state < (1 << n); ++state) {
            if (f[state] == -1) continue;
            for (const auto &s : stickers) {
                int now = state;
                for (char c : s) {
                    for (int i = 0; i < n; ++i) {
                        if ((now >> i) & 1) continue;
                        if (target[i] == c) {
                            now |= (1 << i);
                            break;
                        }
                    }
                }
                if (f[now] == -1 || f[now] > f[state] + 1) {
                    f[now] = f[state] + 1;
                }
            }
        }
        return f.back();
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.6k Reading time ≈ 3 mins.

这道题的前提是不能有相同海拔且海拔高度必须从0到n2-1
类dijkstra O(n2logn) time O(n2) space
这道题的难点是能看出来这其实是一个求最大边费用最小的最短路径（dijkstra）的题（和传统的求最小费用和的最短路径不一样），从一个点到邻居点的费用就是邻居点的海拔高度，这道题需要用dijkstra找到一条路径，使得路径上所有点的最高海拔高度尽可能小（这样就能用最少的时间从起点到终点），因为要维护尽可能小的海拔高度，所以要用堆，每次用堆顶的点的海拔高度来更新全局海拔高度，并将该点的邻接点入堆，至于选择四个方向的哪个邻居，完全基于贪心（dijkstra的本质），反正四个方向的邻居我们都会缓存起来，这样每次更新后实际上都会得到一个更大范围的包含最短路径的区域，在这道题里，这个区域的大小等于这个区域的海拔落差（最高海拔），并且该最短路径一定要经过这个最高海拔的点，因为（反证法）如果能找到另一条路径且最高海拔的点j比结果的最高海拔i要低，那么点j一定在点i之前入堆，且点i不可能入堆
跟1102. Path With Maximum Minimum Value 思路完全一样

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 swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        auto cmp = [&](const pair<int, int> &lhs, const pair<int, int> &rhs) {return grid[lhs.first][lhs.second] > grid[rhs.first][rhs.second];};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        q.emplace(0, 0);
        vector<vector<bool>> visited(n, vector<bool>(n));
        visited[0][0] = true;
        int res = 0;
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto p = q.top(); q.pop();
            res = max(res, grid[p.first][p.second]);
            if (p.first == n - 1 && p.second == n - 1) return res;
            for (int i = 0; i < 4; ++i) {
                int r = p.first + dr[i], c = p.second + dc[i];
                if (0 <= r && r < n && 0 <= c && c < n && !visited[r][c]) {
                    q.emplace(r, c);
                    visited[r][c] = true;
                }
            }
        }
        return -1;
    }
};

采用队列进行局部优化后

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
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        auto cmp = [&](const pair<int, int> &lhs, const pair<int, int> &rhs) {return grid[lhs.first][lhs.second] > grid[rhs.first][rhs.second];};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        vector<vector<bool>> visited(n, vector<bool>(n));
        visited[0][0] = true;
        int res = 0;
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto p = pq.top(); pq.pop();
            res = max(res, grid[p.first][p.second]);
            queue<pair<int, int>> q;
            q.push(p);
            while (!q.empty()) {
                auto p = q.front(); q.pop();
                if (p.first == n - 1 && p.second == n - 1) return res;
                for (int i = 0; i < 4; ++i) {
                    int r = p.first + dr[i], c = p.second + dc[i];
                    if (0 <= r && r < n && 0 <= c && c < n && !visited[r][c]) {
                        if (grid[r][c] <= res) {
                            q.emplace(r, c);
                        } else {
                            pq.emplace(r, c);
                        }
                        visited[r][c] = true;
                    }
                }
            }
        }
        return -1;
    }
};

二分+dfs O(n2logn) time
因为所有的海拔高度是从0到n2-1分布且最后答案一定在grid里面，所以适用二分查找，对于每一个candidate值，dfs遍历整个grid看是否能在candidate值以内（不超过）找到一条从grid[0][0]到grid[n - 1][n - 1]的路径

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:
    int swimInWater(vector<vector<int>>& grid) {
        n = grid.size();
        int lo = 0, hi = n * n - 1;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(grid, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<vector<int>> &grid, int mx) {
        vector<vector<bool>> visited(n, vector<bool>(n));
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        return dfs(grid, visited, 0, 0, mx, dr, dc);
    }

    bool dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int r, int c, int mx, int dr[], int dc[]) {
        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] > mx) return false;
        if (r == n - 1 && c == n - 1) return true;
        visited[r][c] = true;
        for (int i = 0; i < 4; ++i) {
            if (dfs(grid, visited, r + dr[i], c + dc[i], mx, dr, dc)) return true;
        }
        return false;
    }

    int n = 0;
};

Posted on Edited on In Disqus:
Symbols count in article: 3.3k Reading time ≈ 3 mins.

最小边费用最大的最短路径O(RClogRC) time O(RC) space
跟778. Swim in Rising Water思路完全一样
类dijkstra
用最大堆 只找大数 然后沿着大数走 同时用大数来更新结果 直到达到目的地

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
class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<bool>> visited(R, vector<bool>(C));
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] < A[b.first][b.second]; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        visited[0][0] = true;
        int res = INT_MAX, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto [r, c] = pq.top(); pq.pop();
            res = min(res, A[r][c]);

            if (r == R - 1 && c == C - 1) return res;
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[rr][cc]) {
                    pq.emplace(rr, cc);
                    visited[rr][cc] = true;
                }
            }

        }
        return res;
    }
};
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 Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<bool>> visited(R, vector<bool>(C));
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] < A[b.first][b.second]; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        visited[0][0] = true;
        int res = INT_MAX, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto [r, c] = pq.top(); pq.pop();
            res = min(res, A[r][c]);

            // 优化：找出从(r, c)开始的一个范围，该范围内的所有点的费用都不超过A[r][c]
            // 因为用的是queue，不用入堆，局部上使用了复杂度更低的数据结构，但整体的检查规模并没有本质变化
            queue<pair<int, int>> q;
            q.emplace(r, c);
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                if (r == R - 1 && c == C - 1) return res;
                for (int i = 0; i < 4; ++i) {
                    int rr = r + dr[i], cc = c + dc[i];
                    if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[rr][cc]) {
                        if (A[rr][cc] < res) {
                            pq.emplace(rr, cc);
                        } else { // 不小于结果的数不会对结果产生影响，继续扩大局部搜索区域
                            q.emplace(rr, cc);
                        }
                        visited[rr][cc] = true;
                    }
                }
            }

        }
        return res;
    }
};

union-find

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
class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = size(A), C = size(A[0]);
        parent.resize(R * C);
        iota(begin(parent), end(parent), 0);
        vector<pair<int, int>> v;
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                v.emplace_back(r, c);
            }
        }
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] > A[b.first][b.second]; };
        sort(begin(v), end(v), cmp);
        vector<bool> visited(R * C);
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        for (const auto &[r, c] : v) {
            int k = r * C + c;
            visited[k] = true;
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i], kk = rr * C + cc;
                if (rr < 0 || rr >= R || cc < 0 || cc >= C || !visited[kk]) continue;
                merge(k, kk); // 只有visit过的才去union，否则代码不好写
            }
            if (find(0) == find(R * C - 1)) return A[r][c];
        }
        return -1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x), py = find(y);
        parent[py] = px;
    }

    vector<int> parent;
};

Posted on Edited on In Disqus:
Symbols count in article: 858 Reading time ≈ 1 mins.

O(1) time O(n) space

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
class TicTacToe {
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) : n(n) {
        v.resize(n);
        h.resize(n);
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    int move(int row, int col, int player) {
        int s = (player << 1) - 3;
        if (abs(h[row] += s) == n) return player;
        if (abs(v[col] += s) == n) return player;
        if (abs(d += (row == col) * s) == n) return player;
        if (abs(ad += (row + col == n - 1) * s) == n) return player;
        return 0;
    }

    int n;
    vector<int> v, h;
    int d = 0, ad = 0;
};

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe* obj = new TicTacToe(n);
 * int param_1 = obj->move(row,col,player);
 */