Mind palace

some thoughts

0%

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

preorder 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
/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(begin(nums), end(nums));
    }

private:
    typedef vector<int>::iterator Iter;

    TreeNode *sortedArrayToBST(Iter b, Iter e) {
        if (b == e) return nullptr;
        auto m = b + (e - b) / 2;
        auto res = new TreeNode(*m);
        res->left = sortedArrayToBST(b, m);
        res->right = sortedArrayToBST(m + 1, e);
        return res;
    }
};

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

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int fib(int N) {
        int a = 0, b = 1;
        for (int i = 0; i < N; ++i) {
            int t = a;
            a = b;
            b += t;
        }
        return a;
    }
};

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

dp O(mn) time O(mn) space
需要注意边界条件
f[0][0] = grid[0][0]
f[0][j] = f[0][j - 1] + grid[0][j]
f[i][0] = f[i - 1][0] + grid[i][0]
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MAX));
        f[1][0] = 0; // 这行必须有
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return f[m][n];
    }
};

O(mn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[j] = min(f[j], f[j - 1]) + grid[i - 1][j - 1];
            }
            f[0] = INT_MAX; // 只有最开始f[0] = 0后边都是INT_MAX
        }
        return f[n];
    }
};

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

跟104. Maximum Depth of Binary Tree对比
这道题要特别注意一个corner case
[1,2]的mindepth是2不是1
所以不能简单的一行递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int l = minDepth(root->left), r = minDepth(root->right);
        if (!root->left) return r + 1;
        return root->right ? min(l, r) + 1 : l + 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
/**
 * 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:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        int res = INT_MAX;
        if (root->left) {
            res = min(res, minDepth(root->left));
        }
        if (root->right) {
            res = min(res, minDepth(root->right));
        }
        return res + 1;
    }
};

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

topological sort
bfs O(n)

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
class Solution {
public:
    struct P { int indeg = 0; vector<int> children; };
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        int n = numCourses;
        vector<P> courses(n);
        unordered_set<int> zero_indeg;
        for (int i = 0; i < n; ++i) zero_indeg.insert(i);
        for (const auto &p : prerequisites) {
            courses[p.second].children.push_back(p.first);
            ++courses[p.first].indeg;
            zero_indeg.erase(p.first);
        }
        vector<int> res;
        while (!zero_indeg.empty()) {
            int c = *zero_indeg.begin();
            res.push_back(c);
            zero_indeg.erase(c);
            for (auto child : courses[c].children) {
                --courses[child].indeg;
                if (courses[child].indeg == 0) {
                    zero_indeg.insert(child);
                }
            }
        }
        if (res.size() < n) return {};
        return res;
    }
};

dfs O(n)

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:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        n = numCourses;
        visited.resize(n);
        g.resize(n);
        for (const auto &p : prerequisites) {
            g[p[1]].push_back(p[0]);
        }
        for (int i = 0; i < n; ++i) {
            if (dfs(i)) return {};
        }
        return vector<int>(rbegin(s), rend(s));
    }

    bool dfs(int c) {
        if (visited[c] != 0) return visited[c] == -1;
        visited[c] = -1;
        for (auto child : g[c]) {
            if (dfs(child)) return true;
        }
        visited[c] = 1;
        s.push_back(c);
        return false;
    }

    int n;
    vector<int> visited;
    vector<int> s;
    vector<vector<int>> g;
};
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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        n = numCourses;
        visited.resize(n);
        g.resize(n);
        for (const auto &p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        for (int i = 0; i < n; ++i) {
            if (dfs(i)) return {}; // true意味着有圈
        }
        vector<int> res;
        while (!s.empty()) {
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }

    bool dfs(int c) {
        if (visited[c] == 1) return false; // 1表示无圈已访问过，0表示未访问，-1表示不知道有没有圈但是已访问过
        if (visited[c] == -1) return true; // -1说明有圈
        visited[c] = -1;
        for (auto child : g[c]) {
            if (dfs(child)) return true;
        }
        visited[c] = 1;
        s.push(c);
        return false;
    }

    int n;
    vector<int> visited;
    stack<int> s;
    vector<vector<int>> g;
};

Posted on Edited on In Disqus:
Symbols count in article: 618 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
/**
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<pair<TreeNode *, bool>> s;
        s.emplace(root, false);
        vector<int> res;
        while (!s.empty()) {
            auto [x, v] = s.top(); s.pop();
            if (!x) continue;
            if (v) {
                res.push_back(x->val);
            } else {
                s.emplace(x, true);
                s.emplace(x->right, false);
                s.emplace(x->left, false);
            }
        }
        return res;
    }
};

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

快慢指针O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto slow = head, fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true; // 因为slow和fast都是从head开始，所以不能把这个判断条件放在最开始
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        auto slow = head, fast = head;
        do {
            slow = slow->next;
            fast = fast->next->next;
        } while (fast && fast->next && slow != fast);
        return slow == fast;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        auto slow = head, fast = head->next;
        while (fast && fast->next && slow != fast) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow == fast;
    }
};

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

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* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return nullptr;
        if (!t1) return t2;
        if (!t2) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

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

dp O(mn) time O(m) space

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 maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> dp(m + 1);
        int res = 0, pre = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int t = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = min(dp[j - 1], min(dp[j], pre)) + 1;
                } else {
                    dp[j] = 0;
                }
                res = max(res, dp[j]);
                pre = t; // 用pre来cache同一行之前需要计算的值，即f[i][j - 1]
            }
        }
        return res * res;
    }
};

dp + rolling array O(mn) time O(m) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(2, vector<int>(m + 1));
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i % 2][j] = min(dp[i % 2][j - 1], min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1])) + 1;
                } else {
                    dp[i % 2][j] = 0;
                }
                res = max(res, dp[i % 2][j]);
            }
        }
        return res * res;
    }
};

dp O(mn) time O(mn) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res * res;
    }
};

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

O(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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node dummy, *p = &dummy, *res = root;
        while (root) {
            if (root->left) {
                p->next = root->left;
                root->left->next = root->right;
                p = root->right;
            }
            root = root->next;
            if (!root) {
                root = dummy.next;
                dummy.next = nullptr;
                p = &dummy;
            }
        }
        return res;
    }
};

直接用117. Populating Next Right Pointers in Each Node II的方法也行

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* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node dummy, *p = &dummy, *res = root;
        while (root) {
            if (root->left) {
                p->next = root->left;
                p = p->next;
            }
            if (root->right) {
                p->next = root->right;
                p = p->next;
            }
            root = root->next;
            if (!root) {
                root = dummy.next;
                dummy.next = nullptr;
                p = &dummy;
            }
        }
        return res;
    }
};

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
31
32
33
34
35
36
37
38
39
40
41
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        Node dummy_head, *tail = &dummy_head;
        for (auto p = root; p; p = p->next) {
            if (p->left) {
                tail->next = p->left;
                tail = tail->next;
            }
            if (tail->next) break;
            if (p->right) {
                tail->next = p->right;
                tail = tail->next;
            }
            if (tail->next) break;
        }
        connect(root->right);
        connect(root->left);
        return root;
    }
};