Mind palace

some thoughts

0%

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

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
/**
 * 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 kthSmallest(TreeNode* root, int k) {
        int res = 0;
        dfs(root, k, res);
        return res;
    }

    void dfs(TreeNode *root, int &k, int &res) {
        if (!root) return;
        dfs(root->left, k, res);
        if (--k == 0) {
            res = root->val;
            return;
        }
        dfs(root->right, k, res);
    }
};

follow up 给每个节点加一个count来记录当前节点这棵树的所有节点的个数，初始化为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
50
51
52
53
/**
 * 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 kthSmallest(TreeNode* root, int k) {
        TreeNodeWithCount *node = buildTree(root);
        return kthSmallest(node, k);
    }

private:
    struct TreeNodeWithCount {
        int val;
        int count;
        TreeNodeWithCount *left;
        TreeNodeWithCount *right;
        TreeNodeWithCount(int x) : val(x), count(1), left(nullptr), right(nullptr) {}
    };

    TreeNodeWithCount * buildTree(TreeNode *root) {
        if (!root)
            return nullptr;
        TreeNodeWithCount *node = new TreeNodeWithCount(root->val);
        node->left = buildTree(root->left);
        node->right = buildTree(root->right);
        if (node->left)
            node->count += node->left->count;
        if (node->right)
            node->count += node->right->count;
        return node;
    }

    int kthSmallest(TreeNodeWithCount *root, int k) {
        if (root->left) {
            if (root->left->count >= k)
                return kthSmallest(root->left, k);
            if (root->left->count == k - 1)
                return root->val;
            return kthSmallest(root->right, k - 1 - root->left->count);
        }
        else {
            if (k == 1)
                return root->val;
            return kthSmallest(root->right, k - 1);
        }
    }
};

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

O(m+n) time O(m+n) space
前序遍历拼唯一可能的字符串再跑rolling hash版的字符串查找

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
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        dfs(s, ss);
        dfs(t, st);
        return find(ss, st) != -1;
    }

    void dfs(TreeNode *p, string &s) { // 前序遍历拼字符串
        if (!p) {
            s += " #";
            return;
        }
        s += " " + to_string(p->val);
        dfs(p->left, s);
        dfs(p->right, s);
    }

    string ss, st;

    int find(const string &haystack, const string &needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256; // INT_MAX是质数！
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i < h - n + 1; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh && haystack.substr(i, n) == needle) {
                return i;
            }
        }
        return -1;
    }
};

O(m2+n2+mn) time考虑到字符串拼接也要花时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 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 isSubtree(TreeNode* s, TreeNode* t) {
        return preorder(s).find(preorder(t)) != string::npos;
    }

    string preorder(TreeNode *root) {
        return " " + (root ? to_string(root->val) + preorder(root->left) + preorder(root->right) : "#");
    }
};

O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && t) return false; // 防止s为空导致segv
        return isSame(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool isSame(TreeNode *s, TreeNode *t) {
        if (!s && !t) return true;
        if (!s || !t) return false;
        return s->val == t->val && isSame(s->left, t->left) && isSame(s->right, t->right);
    }
};

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

DFS O(n2)
n次标记，每次标记需要扫描n个city，递归深度最多为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
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        n = M.size();
        visited.resize(n);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visit(M, i);
                ++res;
            }
        }
        return res;
    }

    void visit(const vector<vector<int>> &M, int u) {
        visited[u] = true;
        for (int v = 0; v < n; ++v) { // 这里必须从0开始，因为访问u的时候，小于u的并不一定已经被访问过，为了dfs把所有相关的都访问到，必须从0开始
            if (!visited[v] && M[u][v]) {
                visit(M, v);
            }
        }
    }

    int n;
    vector<bool> 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
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        vector<bool> visited(n);
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(M, i, visited);
                ++count; // 每run一次dfs就能找到一个cycle，此时update count
            }
        }
        return count;
    }

    void dfs(const vector<vector<int>> &M, int i, vector<bool> &visited) {
        for (int j = 0; j < M.size(); ++j) {
            if (M[i][j] && !visited[j]) {
                visited[j] = true;
                dfs(M, j, visited);
            }
        }
    }
};

union-find amortized O(n2)

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 Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        UF uf(n);
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j]) {
                    uf.merge(i, j);
                }
            }
        }
        return uf.count;
    }

    struct UF {
        UF(int n) : count(n) {
            parent.resize(n);
            iota(parent.begin(), parent.end(), 0);
        }

        int getParent(int x) {
            while (parent[parent[x]] != parent[x]) {
                x = parent[x] = parent[parent[x]];
            }
            return parent[x];
        }

        void merge(int x, int y) {
            int px = getParent(x);
            int py = getParent(y);
            if (px != py) {
                parent[px] = py;
                --count;
            }
        }

        vector<int> parent;
        int count;
    };
};

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

左下到右上二分 O(m+n) time O(1) space
这道题跟74. Search a 2D Matrix的区别是从左上到右下并非严格递增，所以不能直接用全矩阵二分（复杂度更低）不过这个方法是可以用到那道题上的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int r = m - 1, c = 0;
        while (r >= 0 && c < n) {
            if (matrix[r][c] == target) return true;
            if (matrix[r][c] > target) {
                --r;
            } else {
                ++c;
            }
        }
        return false;
    }
};

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

区间型dp O(n2) time O(n2) space
f[i][j]表示s[i:j]最长回文子序列的长度

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:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (int i = 0; i < n - 1; ++i) {
            f[i][i + 1] = (s[i] == s[i + 1]) + 1;
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0, j = i + len; i < n && j < n; ++i, ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = 2 + f[i + 1][j - 1];
                } else {
                    f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                }
            }
        }
        return f[0][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
            for (int j = i - 1; j >= 0; --j) {
                if (s[i] == s[j]) {
                    dp[j][i] = dp[j + 1][i - 1] + 2;
                } else {
                    dp[j][i] = max(dp[j + 1][i], dp[j][i - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 642 Reading time ≈ 1 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode smaller, larger, *s = &smaller, *l = &larger;
        for (auto p = head; p; p = p->next) {
            if (p->val < x) {
                s->next = p;
                s = s->next;
            } else {
                l->next = p;
                l = l->next;
            }
        }
        s->next = larger.next;
        l->next = nullptr;
        return smaller.next;
    }
};

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

O(n) time O(n) space
证明：
任何一个元素a[i]出现在任何一个位置j的概率是1/n
三种情况讨论（直接用情况1足以）：

  1. i < j P(i) = ((n - 1) / n) * ((n - 2) / (n - 1)) * … * (j / (j + 1)) * (1 / j) = (j / n) * (1 / j) = P(a[i]之前没放在位置j) * P(a[i]这次放在位置j) = 1 / n
  2. i = j P(i) = (j / n) * (1 / j) = 1 / n
  3. i > j P(i) = (j / n) * (1 / j) = 1 / 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
class Solution {
public:
    Solution(vector<int> nums) : nums(nums) {
        srand((unsigned)time(NULL));
    }

    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums;
    }

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        auto res = nums;
        int n = res.size();
        for (int i = n - 1; i > 0; --i) {
            swap(res[rand() % (i + 1)], res[i]);
        }
        return res;
    }

    vector<int> nums;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */

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

O(sqrt(n))
n2 - (n - 1)2 = (n + (n - 1)) * (n - (n - 1)) = 2n-1
e.g., 16 = 1 + 3 + 5 + 7

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isPerfectSquare(int num) {
        for (int i = 1; num > 0; i += 2) {
            num -= i;
        }
        return num == 0;
    }
};

用这个
O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) { // 小于等于可行，因为只需要找
            long m = l + (r - l) / 2;
            long p = m * m;
            if (p == num) {
                return true;
            } else if (p < num) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return false;
    }
};

Newton method

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isPerfectSquare(int num) {
        long x = num;
        while (x * x > num) {
            x = (x + num / x) >> 1;
        }
        return x * x == num;
    }
};

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

binary search O(logx)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int mySqrt(int x) {
        long lo = 0, hi = x; // 一定要从0开始
        while (lo < hi) { // 这道题用小于比较好（<=也行）因为不一定取到精确值
            long m = (lo + hi + 1) / 2, s = m * m; // 注意必须是long防止溢出，并且要+1来取m
            if (s <= x) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        return lo;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int mySqrt(int x) {
        long min = 0, max = x;
        while (min <= max) { // 一定是min <= max而不是min < max是因为最后一定要是min > max来跳出循环，min == max是合法的
            long mid = (min + max) / 2;
            long p = mid * mid;
            if (p == x) {
                return mid;
            }
            else if (p < x) {
                min = mid + 1;
            }
            else {
                max = mid - 1;
            }
        }
        return max; // 是max而不是min是因为最后二分查找一定结束在一个较小的数上，比如5是2而不是3，10是3而不是4，而min一定要比max大才能跳出while循环
    }
};

newton’s method O(logx)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return r;
    }
};

double版

1
2
3
4
5
6
7
8
9
10
11
12
double s(double x) {
	double lo = 0, hi = max(x, 1.0);
	while ((hi - lo) > 1e-8) {
		auto m = (lo + hi) / 2, p = m * m;
		if (p <= x) {
			lo = m;
		} else {
			hi = m;
		}
	}
	return lo;
}

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

O(log(mn)) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty())
            return false;
        int m = matrix.size(), n = matrix[0].size(), l = 0, r = m * n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            int x = matrix[m / n][m % n];
            if (x == target) return true;
            if (x < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return false;
    }
};