Shawn's Blog

Posted 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
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];
        }
    }
};
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        UF uf(tot);
        for (int i = 0; i < n; i += 2)
            uf._union(row[i] / 2, row[i + 1] / 2);
        unordered_map<int, int> m;
        for (int i = 0; i < tot; ++i)
            ++m[uf.find(i)];
        int ans = 0;
        // for each connected set with "sz" as size,
        // "sz - 1" would be the number of needed swaps.
        for (const auto& [_, sz] : m)
            ans += sz - 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
33
34
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> visited(tot, false);
        int ans = 0;
        for (int i = 0; i < tot; ++i)
            if (!visited[i]) {
                queue<int> q;
                q.push(i);
                visited[i] = true;
                int cnt = 0;
                while (!q.empty()) {
                    int x = q.front(); q.pop();
                    ++cnt;
                    for (int nx : graph[x])
                        if (!visited[nx]) {
                            q.push(nx);
                            visited[nx] = true;
                        }
                }
                ans += cnt - 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 minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> seen(tot, false);
        int cnt = 0, ans = 0;
        function<void(int)> dfs = [&](int x) {
            ++cnt;
            for (int nx : graph[x])
                if (!seen[nx]) {
                    seen[nx] = true;
                    dfs(nx);
                };
        };
        for (int i = 0; i < tot; ++i)
            if (!seen[i]) {
                seen[i] = true;
                dfs(i);
                ans += cnt - 1;
                cnt = 0;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(), ans = 0;
        vector<int> ptn(n); // self label -> partner label
        vector<int> pos(n); // label -> seat
        for (int i = 0; i < n; ++i) {
            ptn[i] = i ^ 1;
            pos[row[i]] = i;
        }
        for (int i = 0; i < n; ++i)
            for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
                swap(row[i], row[j]);
                swap(pos[row[i]], pos[row[j]]);
                ++ans;
            }
        return ans;
    }
};

Reference: Java/C++ O(N) solution using cyclic swapping - LeetCode Discuss.

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (int num : nums) {
            int idx = (num - 1) % n;
            nums[idx] += n;
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i)
            if (nums[i] <= n)
                ans.emplace_back(i + 1);
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size() - 1, ans = 0;
        for (int i = 0; i < n; ++i) 
            ans += max(0, prices[i + 1] - prices[i]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            cash = max(cash, hold + prices[i]);
            hold = max(hold, cash - prices[i]);
        }
        return cash;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX, max_profit = 0;
        for (int price : prices) {
            max_profit = max(max_profit, price - min_price);
            min_price = min(min_price, price);
        }
        return max_profit;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for (int i = 1; i < n; ++i) {
            triangle[i][0] += triangle[i - 1][0];
            triangle[i][i] += triangle[i - 1][i - 1];
            for (int j = 1; j < i; ++j)
                triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
        }
        return *min_element(triangle[n - 1].begin(), triangle[n - 1].end());
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int row = 0; row < numRows; ++row) {
            ans[row].resize(row + 1);
            ans[row][0] = ans[row][row] = 1;
            for (int col = 1; col < row; ++col)
                ans[row][col] = ans[row - 1][col - 1] + ans[row - 1][col];
        }
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i)
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        return row;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> q;
    int k;
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (auto& x: nums)
            add(x);
    }
    int add(int val) {
        q.push(val);
        if (q.size() > k)
            q.pop();
        return q.top();
    }
};

Posted on In 
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:
    string minWindow(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2) return "";
        vector<int> freq(128);
        for (char c : t)
            freq[c]++;
        int left = 0, right = 0, minWinLen = INT_MAX, head = 0;
        while (right < n1) {
            if (freq[s[right++]]-- > 0)
                --n2; // char in t.
            while (n2 == 0) { // valid window.
                if (right - left < minWinLen)
                    minWinLen = right - (head = left); // get min window length.
                if (freq[s[left++]]++ == 0)
                    n2++;
            }
        }
        return minWinLen == INT_MAX ? "" : s.substr(head, minWinLen);
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MedianFinder {
private:
    vector<int> data;
public:
    MedianFinder() {
    }
    void addNum(int num) {
        if (data.empty())
            data.emplace_back(num);
        else
            data.insert(lower_bound(data.begin(), data.end(), num), num);
    }
    double findMedian() {
        int n = data.size();
        return n & 1 ? data[n / 2] : (data[n / 2 - 1] + data[n / 2]) * 0.5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MedianFinder {
private:
    priority_queue<int> lo; // max heap
    priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
    MedianFinder() {
    }
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        if (lo.size() < hi.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }
    double findMedian() {
        return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};
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 MedianFinder {
private:
    multiset<int> data;
    multiset<int>::iterator lo, hi;
public:
    MedianFinder(): lo(data.end()), hi(data.end()) {
    }
    void addNum(int num) {
        const int n = data.size();
        data.insert(num);
        if (!n) { // the 1st element.
            lo = hi = data.begin();
        } else if (n & 1) { // odd size before.
            if (num < *lo) --lo;
            else ++hi;
        } else { // even size before.
            if (num > *lo && num < *hi) {
                ++lo;
                --hi;
            } else if (num >= *hi) ++lo;
            else lo = --hi;
        }
    }
    double findMedian() {
        return (*lo + *hi) * 0.5;
    }
};
0%