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
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        vector<int> f(s.size(), -1);
        vector<vector<int>> m(s.size());
        if (pairs.size() == 0) return s;
        for (auto& p : pairs) {
            auto i = find(f, p[0]), j = find(f, p[1]);
            if (i != j) {
                if (-f[i] < -f[j])
                    swap(i ,j);
                f[i] += f[j];
                f[j] = i;
            }
        }
        for (int i = 0; i < s.size(); ++i)
            m[find(f, i)].push_back(i);
        for (auto& ids : m) {
            string ss = "";
            for (int id : ids)
                ss += s[id];
            sort(ss.begin(), ss.end());
            for (int i = 0; i < ids.size(); ++i)
                s[ids[i]] = ss[i];
        }
        return s;
    }
    int find(vector<int>& f, int i) {
        return f[i] < 0 ? i : f[i] = find(f, f[i]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        class UF:
            def __init__(self, n): self.p = list(range(n))
            def union(self, x, y): self.p[self.find(x)] = self.find(y)
            def find(self, x):
                if x != self.p[x]: self.p[x] = self.find(self.p[x])
                return self.p[x]
        uf, m, ans = UF(len(s)), defaultdict(list), []
        for a, b in pairs: 
            uf.union(a, b)
        for i in range(len(s)): 
            m[uf.find(i)].append(s[i])
        for id in m.keys(): 
            m[id].sort(reverse=True)
        for i in range(len(s)): 
            ans.append(m[uf.find(i)].pop())
        return ''.join(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
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        if (nums.size()) {
            int start = nums[0];
            for (int i = 1; i < nums.size(); ++i) {
                if (nums[i] != nums[i - 1] + 1) {
                    if (start == nums[i - 1])
                        ans.push_back(to_string(start));
                    else
                        ans.push_back(to_string(start) + "->" + to_string(nums[i - 1]));
                    start = nums[i];
                }
            }
            if (start == nums.back())
                ans.push_back(to_string(nums.back()));
            else
                ans.push_back(to_string(start) + "->" + to_string(nums.back()));
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i)
            newArr[(i + k) % n] = nums[i];
        nums.assign(newArr.begin(), newArr.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        const int n = nums.size();
        k %= n;
        int cnt = gcd(n, k);
        for (int start = 0; start < cnt; ++start) {
            int currIndex = start;
            int currVal = nums[currIndex];
            do {
                int nextIndex = (currIndex + k) % n;
                int nextVal = nums[nextIndex];
                nums[nextIndex] = currVal;
                currIndex = nextIndex;
                currVal = nextVal;
            } while (currIndex != start);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end)
            swap(nums[start++], nums[end--]);
    }
};

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
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        vector<bool> visited(N, false);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(M, i, visited);
            }
        return cnt;
    }
private:
    void dfs(vector<vector<int>>& M, int i, vector<bool>& visited) {
        visited[i] = true;
        for (int j = 0; j < M.size(); ++j)
            if (M[i][j] && !visited[j])
                dfs(M, j, visited);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        vector<bool> visited(N, false);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(M, i, visited);
            }
        return cnt;
    }
private:
    void dfs(vector<vector<int>>& M, int i, vector<bool>& visited) {
        visited[i] = true;
        for (int j = 0; j < M.size(); ++j)
            if (M[i][j] && !visited[j])
                dfs(M, j, visited);
    }
};
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 findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        for (int i = 0; i < N; ++i)
            f.push_back(i);
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                if (M[i][j])
                    _union(i, j);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (f[i] == i)
                ++cnt;
        return cnt;
    }
private:
    vector<int> f;
    int find(int i) {
        int j = i;
        while (f[i] != i)
            i = f[i];
        while (j != i) {
            int next = f[j];
            f[j] = i;
            j = next;
        }
        return i;
    }
    void _union(int i, int j) {
        f[find(i)] = find(j);
    }
};

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
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<vector<pair<int, double>>> edges(varCnt);
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            edges[leftVar].emplace_back(rightVar, values[i]);
            edges[rightVar].emplace_back(leftVar, 1.0 / values[i]);
        }
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() & variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                if (leftIndex == rightIndex)
                    result = 1.0;
                else {
                    queue<int> points;
                    points.push(leftIndex);
                    vector<double> ratios(varCnt, -1);
                    ratios[leftIndex] = 1.0;
                    vector<bool> visited(varCnt, false);
                    while (!points.empty() && ratios[rightIndex] == -1) {
                        leftIndex = points.front(); points.pop();
                        for (const auto [nextIndex, val] : edges[leftIndex]) {
                            if (ratios[nextIndex] == -1) {
                                ratios[nextIndex] = ratios[leftIndex] * val;
                                points.push(nextIndex);
                            }
                        }
                    }
                    result = ratios[rightIndex];
                }
            }
            ans.push_back(result);
        }
        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
35
36
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<vector<double>> graph(varCnt, vector<double>(varCnt, -1.0));
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            graph[leftVar][rightVar] = values[i];
            graph[rightVar][leftVar] = 1.0 / values[i];
        }
        for (int k = 0; k < varCnt; ++k)
            for (int i = 0; i < varCnt; ++i)
                for (int j = 0; j < varCnt; ++j)
                    if (graph[i][k] != -1 && graph[k][j] != -1)
                        graph[i][j] = graph[i][k] * graph[k][j];
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                if (graph[leftIndex][rightIndex] != -1)
                    result = graph[leftIndex][rightIndex];
            }
            ans.push_back(result);
        }
        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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int varCnt = 0;
        unordered_map<string, int> variables;
        const int n = equations.size();
        for (int i = 0; i < n; ++i) {
            if (variables.find(equations[i][0]) == variables.end())
                variables[equations[i][0]] = varCnt++;
            if (variables.find(equations[i][1]) == variables.end())
                variables[equations[i][1]] = varCnt++;
        }
        vector<int> f(varCnt);
        vector<double> w(varCnt, 1.0);
        for (int i = 0; i < varCnt; ++i)
            f[i] = i;
        for (int i = 0; i < n; ++i) {
            int leftVar = variables[equations[i][0]], rightVar = variables[equations[i][1]];
            merge(f, w, leftVar, rightVar, values[i]);
        }
        vector<double> ans;
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int leftIndex = variables[q[0]], rightIndex = variables[q[1]];
                int fl = findf(f, w, leftIndex), fr = findf(f, w, rightIndex);
                if (fl == fr)
                    result = w[leftIndex] / w[rightIndex];
            }
            ans.push_back(result);
        }
        return ans;
    }
private:
    int findf(vector<int>& f, vector<double>& w, int x) {
        if (x != f[x]) {
            int father = findf(f, w, f[x]);
            w[x] = w[x] * w[f[x]];
            f[x] = father;
        }
        return f[x];
    }
    void merge(vector<int>& f, vector<double>& w, int x, int y, double val) {
        int fx = findf(f, w, x);
        int fy = findf(f, w, y);
        f[fx] = fy;
        w[fx] = val * w[y] / w[x];
    }
};

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
class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        char prev = ' ';
        int start = -1, i = 0;
        vector<vector<int>> ans;
        for (char c : s) {
            if (c != prev) {
                if (i - start >= 3) {
                    ans.push_back(vector<int>{start, i - 1});
                }
                prev = c;
                start = i;
            }
            ++i;
        }
        if (i - start >= 3)
            ans.push_back(vector<int>{start, i - 1});
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

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
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* smallHead = new ListNode(0);
        ListNode* smallCurr = smallHead;
        ListNode* largeHead = new ListNode(0);
        ListNode* largeCurr = largeHead;
        while (head != nullptr) {
            if (head->val < x) {
                smallCurr->next = head;
                smallCurr = smallCurr->next;
            } else {
                largeCurr->next = head;
                largeCurr = largeCurr->next;
            }
            head = head->next;
        }
        smallCurr->next = largeHead->next;
        largeCurr->next = nullptr;
        return smallHead->next;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i)
            q.emplace(nums[i], i);
        vector<int> ans = {q.top().first};
        for (int i = k; i < nums.size(); ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k)
                q.pop();
            ans.push_back(q.top().first);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()])
                q.pop_back();
            q.push_back(i);
        }
        vector<int> ans{nums[q.front()]};
        for (int i = k; i < nums.size(); ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()])
                q.pop_back();
            q.push_back(i);
            while (q.front() <= i - k)
                q.pop_front();
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> prefixMax(n), suffixMax(n);
        for (int i = 0; i < n; ++i)
            if (i % k == 0) prefixMax[i] = nums[i];
            else prefixMax[i] = max(prefixMax[i - 1], nums[i]);
        suffixMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i)
            if ((i + 1) % k == 0) suffixMax[i] = nums[i];
            else suffixMax[i] = max(suffixMax[i + 1], nums[i]);
        vector<int> ans;
        for (int i = 0; i <= n - k; ++i)
            ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));
        return ans;
    }
};
0%