Mind palace

some thoughts

0%

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

right-middle-left reverse order traversal O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return root;
        convertBST(root->right);
        sum = (root->val += sum);
        convertBST(root->left);
        return root;
    }

    int sum = 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        helper(root, sum);
        return root;
    }

    void helper(TreeNode *root, int &sum) {
        if (!root) return;
        helper(root->right, sum);
        root->val += sum;
        sum = root->val;
        helper(root->left, sum);
    }
};

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

右中左序遍历，维护一个全局的sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        if (!root) return root;
        bstToGst(root->right);
        root->val = sum += root->val;
        bstToGst(root->left);
        return root;
    }

    int sum = 0;
};

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

O(mn)↗↙
0 <= sum < m + n - 1
0 <= r < n
0 <= c < m
sum = r + c
0 <= r = sum - c < n即sum - n < c <= sum
0 <= c = sum - r < m即sum - m < r <= sum
所以
max(0, sum - m + 1) <= r <= min(n - 1, sum)
// max(0, sum - n + 1) <= c <= min(m - 1, sum)

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> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int R = matrix.size(), C = matrix[0].size();
        vector<int> res;
        int size = R + C - 1;
        for (int sum = 0; sum < size; ++sum) {
            if (sum & 1) {
                for (int r = max(0, sum - (C - 1)); r <= min(R - 1, sum); ++r) {
                    res.push_back(matrix[r][sum - r]);
                }
            } else {
                for (int r = min(R - 1, sum); r >= max(0, sum - (C - 1)); --r) {
                    res.push_back(matrix[r][sum - r]);
                }
            }
        }
        return res;
    }
};
Read more »

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

bfs+topological sort O(n) time O(n) space
从外往里『剥洋葱』直到还剩1到2个节点为止，如果设置一个超级源点连接每个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
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n < 2) return {0};
        vector<unordered_set<int>> g(n);
        for (const auto &e : edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        list<int> q;
        for (int i = 0; i < n; ++i) {
            if (g[i].size() == 1) { // 叶节点『入度为0』
                q.push_back(i);
            }
        }
        while (n > 2) { // 还剩最多2个『入度为0』的节点时跳出循环，不能直接看队列大小，队列里放的只是当前『入度为0』的节点
            n -= size(q);
            for (int i = size(q); i > 0; --i) {
                int u = q.front(); q.pop_front();
                for (int v : g[u]) {
                    g[v].erase(u); // 从邻居那删除『我』
                    if (g[v].size() == 1) { // 为了避免重复入队列，只有还连着最后一条边的时候再入
                        q.push_back(v);
                    }
                }
            }
        }
        return vector<int>(begin(q), end(q));
    }
};

纯topological sort O(n2) 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
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n < 2) return {0};
        unordered_map<int, unordered_set<int>> g;
        for (const auto &e : edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        vector<int> res;
        while (!g.empty()) {
            res.clear();
            for (const auto &[i, _] : g) {
                if (g.count(i) && g[i].size() < 2) {
                    res.push_back(i);
                }
            }
            for (int u : res) {
                for (int v : g[u]) {
                    g[v].erase(u);
                }
                g.erase(u);
            }
        }
        return res;
    }
};

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

bfs O(mn) time O(min(m, n)) space
先顺四个边给open island灌水 然后遍历grid给每个closed island灌水并统计个数即可

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
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
                    bfs(grid, i, j);
                }
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 0) {
                    bfs(grid, i, j);
                    ++res;
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &grid, int r, int c) {
        queue<pair<int, int>> q;
        grid[r][c] = 1;
        q.emplace(r, c);
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || grid[rr][cc]) continue;
                grid[rr][cc] = 1;
                q.emplace(rr, cc);
            }
        }
    }

    int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                bfs(grid, i, 0);
            }
            if (grid[i][n - 1] == 0) {
                bfs(grid, i, n - 1);
            }
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 0) {
                bfs(grid, 0, j);
            }
            if (grid[m - 1][j] == 0) {
                bfs(grid, m - 1, j);
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 0) {
                    bfs(grid, i, j);
                    ++res;
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &grid, int r, int c) {
        queue<pair<int, int>> q;
        grid[r][c] = 1;
        q.emplace(r, c);
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || grid[rr][cc]) continue;
                grid[rr][cc] = 1;
                q.emplace(rr, cc);
            }
        }
    }

    int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
};

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

翻转链表 O(m+n) time O(1) 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
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        int c = 0;
        ListNode *res = nullptr;
        while (l1 || l2 || c > 0) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
            int s = a + b + c;
            auto x = new ListNode(s % 10);
            x->next = res;
            res = x;
            c = s / 10;
        }
        return res;
    }

    ListNode *reverse(ListNode *l) {
        if (!l) return l;
        ListNode *p = nullptr, *c = l;
        while (c) {
            auto s = c->next;
            c->next = p;
            p = c;
            c = s;
        }
        return p;
    }
};

两个栈 O(m+n) time O(m+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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2; // 两个栈逆序放入两个链表里的数
        for (auto node = l1; node; node = node->next) {
            s1.push(node->val);
        }
        for (auto node = l2; node; node = node->next) {
            s2.push(node->val);
        }
        int a = 0, b = 0, c = 0; // 统一处理 加数 被加数 进位
        ListNode *l = nullptr;
        while (!s1.empty() || !s2.empty() || c > 0) { // 不要忘记最后进位有可能不为0！！！
            a = s1.empty() ? 0 : s1.top();
            b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int s = a + b + c;
            auto n = new ListNode(s % 10);
            n->next = l;
            l = n;
            c = s / 10;
        }
        return l;
    }
};

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

O(m + n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s(nums1.begin(), nums1.end());
        vector<int> res;
        for (int n : nums2) {
            if (s.find(n) != s.end()) {
                res.push_back(n);
                s.erase(n); // if nums2 has multiple copy of n, then the following instances cannot be found any more, in order to avoid duplicate push back
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, bool> m;
        for (int x : nums1) {
            m[x] = true;
        }
        vector<int> res;
        for (int x : nums2) {
            if (m[x]) {
                res.push_back(x);
                m[x] = false; // if nums2 has multiple copy of x, then the following instances cannot be found any more, in order to avoid duplicate push back
            }
        }
        return res;
    }
};

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

用当前价格减去之前的最低价格来更新全局最大差价即可

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

直接切入法
买卖一股，一定是第i天买，第j天卖（j > i），获利是prices[j] - prices[i]
枚举j，即第几天卖，只需要维护当前最低的买入价格prices[i] (i < j)即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int curr_min = INT_MAX;
        int res = 0;
        int n = prices.size();
        for (int i = 0; i < n; ++i) {
            curr_min = min(curr_min, prices[i]);
            res = max(res, prices[i] - curr_min);
        }
        return res;
    }
};

maximum subarray法
dp O(n) time O(1) space

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

dp O(n) time O(n) space
maximum subarray的变体
(b - a) + (c - b) + (d - c) + (e - d) = e - a

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:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        vector<int> diffs(n - 1);
        for (int i = 1; i < n; ++i) {
            diffs[i - 1] = prices[i] - prices[i - 1];
        }
        vector<int> dp(n);
        int res = 0;
        for (int i = 1; i < n; ++i) {
            if (dp[i - 1] < 0) {
                dp[i] = diffs[i - 1];
            } else {
                dp[i] = dp[i - 1] + diffs[i - 1];
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

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

constructor O(1) set O(1) snap O(1) get O(logSnaps)
用这个

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 SnapshotArray {
public:
    SnapshotArray(int length) {
        snaps.resize(length);
    }

    void set(int index, int val) {
        if (snaps[index].empty() || snaps[index].back().first != sid && snaps[index].back().second != val) { // 如果没有index的snap记录或者只有旧的记录（跟新值不同的），添加下一个snap_id的记录
            snaps[index].emplace_back(sid, val);
        } else {
            snaps[index].back().second = val; // 如果已经有下一个snap_id的记录则直接修改即可
        }
    }

    int snap() {
        return sid++;
    }

    int get(int index, int snap_id) {
        auto &v = snaps[index];
        auto it = upper_bound(begin(v), end(v), make_pair(snap_id, INT_MAX)); // 为了找到上界需要使用INT_MAX
        return it == begin(v) ? 0 : prev(it)->second; // 最开始所有元素都为0所以找不着就给0
    }

    vector<vector<pair<int, int>>> snaps; // key是index，pair是sid和val
    int sid = 0; // 下一个snap_id;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

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

O(n) 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
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (const auto &t : tokens) {
            if (t.length() > 1 || isdigit(t[0])) { // 这里切记要检查长度是否大于1，因为有可能是负数！！
                s.push(stoi(t));
            } else {
                int b = s.top(); s.pop();
                int a = s.top(); s.pop();
                switch (t[0]) {
                    case '+': s.push(a + b); break;
                    case '-': s.push(a - b); break;
                    case '*': s.push(a * b); break;
                    case '/': s.push(a / b); break;
                }
            }
        }
        return s.top();
    }
};