Mind palace

some thoughts

0%

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

dp O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int f = 0, res = INT_MIN;
        for (int x : nums) {
            f = max(f, 0) + x;
            res = max(res, f);
        }
        return res;
    }
};

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

bfs 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            unordered_set<int> s;
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); q.pop();
                if (t->left && t->right) {
                    unordered_set<int> temp{t->left->val, t->right->val};
                    if (temp.count(x) && temp.count(y)) return false; // 如果x和y共父，则非法
                }
                s.insert(t->val);
                if (t->left) {
                    q.push(t->left);
                }
                if (t->right) {
                    q.push(t->right);
                }
            }
            if (s.count(x) && s.count(y)) return true; // 搜集当前层所有点，看x和y是不是都存在
            if (s.count(x) || s.count(y)) return false;
        }
        return false;
    }
};

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

O(1) time O(size) 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 MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) : n(size), sum(0) {

    }

    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > n) {
            sum -= q.front();
            q.pop();
        }
        return sum / q.size(); // 切记不能除n！！！因为queue里不一定有n个数
    }

    int n;
    double sum;
    queue<int> q;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

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

recursive O(n) time

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        Node dummy_head;
        dummy_head.next = head;
        helper(head);
        return dummy_head.next;
    }

    Node *helper(Node *head) { // 返回处理以后的最后一个非空node
        if (!head) return head;
        if (head->child) {
            auto succ = head->next;
            head->next = head->child;
            head->child = nullptr;
            head->next->prev = head;
            auto prev = helper(head->next);
            prev->next = succ;
            if (succ) {
                succ->prev = prev;
            }
        }
        return head->next ? helper(head->next) : head;
    }
};

iterative O(n) time
每个node访问两次

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 a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        for (auto p = head; p; p = p->next) {
            if (p->child) {
                auto succ = p->next;
                p->next = p->child;
                p->next->prev = p;
                p->child = nullptr;
                auto tail = p->next;
                while (tail->next) { // 找到最后一个节点跟上一层断点连上
                    tail = tail->next;
                }
                tail->next = succ;
                if (succ) {
                    succ->prev = tail;
                }
            }
        }
        return head;
    }
};

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

O(n) time O(h) 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
/**
 * 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* subtreeWithAllDeepest(TreeNode* root) {
        dfs(root, 1);
        return res;
    }

    int dfs(TreeNode *root, int depth) { // depth是从根到当前结点的深度，返回当前这棵树的深度
        if (!root) return 0;
        int l = dfs(root->left, depth + 1); // 子树的深度
        int r = dfs(root->right, depth + 1);
        if (l == r && depth + l >= mx) { // find the lowest root that covers all the deepest leaves
            mx = depth + l;
            res = root;
        }
        return max(l, r) + 1;
    }

    TreeNode *res = nullptr;
    int mx = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).first;
    }

    pair<TreeNode *, int> dfs(TreeNode *root) {
        if (!root) return {root, 0};
        auto l = dfs(root->left), r = dfs(root->right);
        if (l.second == r.second) return {root, l.second + 1};
        if (l.second > r.second) return {l.first, l.second + 1};
        return {r.first, r.second + 1};
    }
};

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

postorder O(n) time O(h) 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
/**
 * 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* lcaDeepestLeaves(TreeNode* root) {
        dfs(root, 1);
        return res;
    }

    int dfs(TreeNode *root, int depth) { // depth是从根到当前结点的深度，返回当前这棵树的深度
        if (!root) return 0;
        int l = dfs(root->left, depth + 1); // 子树的深度
        int r = dfs(root->right, depth + 1);
        if (l == r && depth + l >= mx) { // find the lowest root that covers all the deepest leaves
            mx = depth + l;
            res = root;
        }
        return max(l, r) + 1;
    }

    TreeNode *res = nullptr;
    int mx = 0;
};

对于当前的这棵树，分别获取左子树和右子树的最深叶节点的lca以及最大深度，如果左右两边最大深度相等，则root是当前这棵树的最深叶节点的lca，返回root以及当前这棵树的最大深度；如果左右两边的最大深度不等，则返回深度较大的那个子树的结果以及当前这棵树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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* lcaDeepestLeaves(TreeNode* root) {
        return dfs(root).first;
    }

    pair<TreeNode *, int> dfs(TreeNode *root) {
        if (!root) return {root, 0};
        auto l = dfs(root->left), r = dfs(root->right);
        if (l.second == r.second) return {root, l.second + 1};
        if (l.second > r.second) return {l.first, l.second + 1};
        return {r.first, r.second + 1};
    }
};

bfs 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 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* lcaDeepestLeaves(TreeNode* root) {
        if (!root) return root;
        unordered_map<TreeNode *, TreeNode *> parent;
        unordered_set<TreeNode *> s;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            s.clear();
            for (int i = q.size(); i > 0; --i) {
                auto n = q.front(); q.pop();
                s.insert(n);
                if (n->left) {
                    q.push(n->left);
                    parent[n->left] = n;
                }
                if (n->right) {
                    q.push(n->right);
                    parent[n->right] = n;
                }
            }
        }
        while (s.size() > 1) {
            unordered_set<TreeNode *> t;
            t.swap(s);
            for (auto n : t) {
                s.insert(parent[n]);
            }
        }
        return *begin(s);
    }
};

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

O(n) time O(1) space
思路就是维护odd和even两个指针，扫一遍链表把odd跟even拆出来，最后odd跟even的head连起来即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        auto odd = head, even = odd->next, even_head = even;
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = even_head;
        return head;
    }
};

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

O(h)

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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (!p || !q) return root;
        auto [s, l] = minmax(p->val, q->val);
        if (s <= root->val && root->val <= l) return root; // 注意等于的case，说明p和q一个是另一个的父节点
        if (root->val < s) return lowestCommonAncestor(root->right, p, q);
        if (l < root->val) return lowestCommonAncestor(root->left, p, q);
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        auto [lo, hi] = minmax(p->val, q->val);
        if (lo <= root->val && root->val <= hi) return root;
        return hi < root->val ? lowestCommonAncestor(root->left, p, q) : lowestCommonAncestor(root->right, p, q);
    }
};

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

dp II跟III的结合版

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 maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        if (k > n / 2) { // 当k超过天数一半则不存在k个交易such that所有交易都不相邻，所以任意多个不相邻的交易的总数都不会超过k个
            int res = 0;
            for (int i = 1; i < n; ++i) {
                res += max(prices[i] - prices[i - 1], 0);
            }
            return res;
        }
        int m = 2 * k + 1;
        vector<vector<int>> f(n, vector<int>(m));
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int diff = prices[i] - prices[i - 1];
                if (j & 1) {
                    f[i][j] = max(f[i - 1][j] + diff, f[i - 1][j - 1]);
                } else {
                    f[i][j] = max(f[i - 1][j], j > 0 ? f[i - 1][j - 1] + diff : 0);
                }
            }
        }
        return *max_element(f[n - 1].begin(), f[n - 1].end());
    }
};
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 maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        if (k > n / 2) {
            int res = 0;
            for (int i = 1; i < n; ++i) {
                res += max(prices[i] - prices[i - 1], 0);
            }
            return res;
        }
        int m = 2 * k + 1;
        vector<int> f(m);
        for (int i = 1; i < n; ++i) {
            for (int j = m - 1; j >= 0; --j) {
                int diff = prices[i] - prices[i - 1];
                if (j & 1) {
                    f[j] = max(f[j] + diff, f[j - 1]);
                } else {
                    f[j] = max(f[j], j > 0 ? f[j - 1] + diff : 0);
                }
            }
        }
        return *max_element(begin(f), end(f));
    }
};

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

类似快慢指针找cycle O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        for (int i = 0; i < indices.size(); ++i) {
            while (i != indices[i]) { // 只要当前位置不是正确的index就一直swap
                swap(s[i], s[indices[i]]); // 保持字符串跟indices数组同步即可
                swap(indices[i], indices[indices[i]]);
            }
        }
        return s;
    }
};