Mind palace

some thoughts

0%

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

O(n2) 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
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dc[] = {0, 1, 1, 1, 0, -1, -1, -1};
        if (grid[0][0] == 1) return -1;
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        grid[0][0] = 1;
        int res = 0;
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                auto [r, c] = q.front(); q.pop();
                if (r == n - 1 && c == n - 1) return res;
                for (int i = 0; i < 8; ++i) {
                    int rr = r + dr[i], cc = c + dc[i];
                    if (0 <= rr && rr < n && 0 <= cc && cc < n && grid[rr][cc] == 0) {
                        q.emplace(rr, cc);
                        grid[rr][cc] = 1;
                    }
                }
            }
        }
        return -1;
    }
};

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

ad-hoc O(n*(n+m)) m是A的长度 n是B的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        string s;
        int cnt = 0;
        while (s.length() < B.length()) {
            ++cnt;
            s += A;
        }
        if (s.find(B) != string::npos) return cnt;
        s += A; // 长度超过B未必一定包含B有可能最后还差A开头的几个字母
        ++cnt;
        return s.find(B) == string::npos ? -1 : cnt;
    }
};

这道题还有KMP和Rabin-Karp (Rolling Hash)两种做法 O(m+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
32
33
34
class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        string s;
        int cnt = 0;
        while (s.length() < B.length()) {
            ++cnt;
            s += A;
        }
        if (strStr(s, B) != -1) return cnt;
        s += A; // 长度超过B未必一定包含B有可能最后还差A开头的几个字母
        ++cnt;
        return strStr(s, B) == -1 ? -1 : cnt;
    }

    int strStr(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; ++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;
    }
};

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

O(n*m*min(n, m2)) 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    int numSimilarGroups(vector<string>& A) {
        int n = A.size(), m = A[0].length();
        res = n;
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        if (n < m * m) {
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (isSimilar(A[i], A[j])) {
                        merge(i, j);
                    }
                }
            }
        } else {
            unordered_map<string, vector<int>> hm;
            for (int i = 0; i < n; ++i) {
                auto s = A[i];
                for (int j = 0; j < m; ++j) {
                    for (int k = j + 1; k < m; ++k) {
                        if (s[j] == s[k]) continue;
                        swap(s[j], s[k]);
                        hm[s].push_back(i); // 把每个词能转换成的词都枚举出来，注意原始词不放进去，后面用来merge
                        swap(s[j], s[k]);
                    }
                }
            }
            for (int i = 0; i < n; ++i) {
                if (hm.count(A[i])) { // 用每个词去找哪些词能转换成这个词
                    for (int j : hm[A[i]]) {
                        merge(i, j);
                    }
                }
            }
        }
        return res;
    }

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

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

    bool isSimilar(const string &a, const string &b) {
        int x = -1, y = -1, n = a.length();
        if (n == 1) return a == b;
        for (int i = 0; i < n; ++i) {
            if (a[i] == b[i]) continue;
            if (x == -1) {
                x = i;
            } else if (y == -1) {
                y = i;
            } else return false;
        }
        return x == -1 || y != -1;
    }

    vector<int> parent;
    int res;
};

用这个
O(nnm) time where n是字符串个数m是字符串长度

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 numSimilarGroups(vector<string>& A) {
        int n = A.size();
        res = n;
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isSimilar(A[i], A[j])) {
                    merge(i, j);
                }
            }
        }
        return res;
    }

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

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

    bool isSimilar(const string &a, const string &b) {
        int x = -1, y = -1, n = a.length();
        if (n == 1) return a == b;
        for (int i = 0; i < n; ++i) {
            if (a[i] == b[i]) continue;
            if (x == -1) {
                x = i;
            } else if (y == -1) {
                y = i;
            } else return false;
        }
        return x == -1 || y != -1; // 两个词要不相同，要不只能有两个字母不一样，前提是所有词都是anagram
    }

    vector<int> parent;
    int res;
};

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

dp O(nlogn) dp[i]是 长度为i+1的递增子序列的 能找到的最小的第i大（最大）元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp;
        for (int i = 0; i < n; ++i) {
            auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
            if (it == dp.end()) {
                dp.push_back(nums[i]);
            } else {
                *it = nums[i];
            }
        }
        return dp.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> f;
        for (int x : nums) {
            auto it = lower_bound(f.begin(), f.end(), x);
            if (it == f.end()) {
                f.push_back(x);
            } else {
                *it = x;
            }
        }
        return f.size();
    }
};

dp O(n2) dp[i]是LIS必须以nums[i]结尾的LIS的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

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

dp优化矩阵乘法 O(logn) time O(1) space
状态转移矩阵用column-based竖着看才行

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
54
55
56
class Solution {
public:
    int knightDialer(int N) {
        vector<vector<long>> mtx = {
            {0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
            {0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
            {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {1, 1, 0, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
            {0, 0, 1, 0, 1, 0, 0, 0, 0, 0}
        };
        mtx = pow(mtx, N - 1);
        vector<vector<long>> f{vector<long>(10, 1)};
        f = mul(f, mtx);
        int res = 0;
        for (int i = 0; i < 10; ++i) {
            res = (res + f[0][i]) % M;
        }
        return res;
    }

    vector<vector<long>> pow(vector<vector<long>> &mtx, int N) {
        int n = mtx.size();
        vector<vector<long>> res(n, vector<long>(n));
        for (int i = 0; i < n; ++i) {
            res[i][i] = 1;
        }
        while (N > 0) {
            if (N & 1) {
                res = mul(res, mtx);
            }
            mtx = mul(mtx, mtx);
            N >>= 1;
        }
        return res;
    }

    vector<vector<long>> mul(const vector<vector<long>> &a, const vector<vector<long>> &b) {
        int m = a.size(), n = b.size(), p = b[0].size();
        vector<vector<long>> res(m, vector<long>(p));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < p; ++j) {
                for (int k = 0; k < n; ++k) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % M;
                }
            }
        }
        return res;
    }

    int M = 1e9 + 7;
};

dp O(N) time O(1) space
bottom up
最底层是N=1每一层往上迭代累加即可
f[i]表示最后一个数为i的可能的拨号方式有多少种
f[i]表示当前层到最底层从i开始的不同number的个数

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 knightDialer(int N) {
        vector<vector<int>> next = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
        int M = 1e9 + 7;
        vector<int> f(10, 1);
        for (int i = 1; i < N; ++i) {
            vector<int> t(10);
            t.swap(f);
            for (int u = 0; u < 10; ++u) {
                for (int v : next[u]) {
                    f[v] = (f[v] + t[u]) % M;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 10; ++i) {
            res = (res + f[i]) % M;
        }
        return res;
    }
};

dfs+memo 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
class Solution {
public:
    int knightDialer(int N) {
        next = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
        m.resize(10, vector<int>(N + 1, -1));
        int res = 0;
        for (int i = 0; i < 10; ++i) {
            res = (res + count(i, N)) % M;
        }
        return res;
    }

    int count(int u, int N) {
        if (N == 1) return 1;
        if (m[u][N] != -1) return m[u][N];
        int res = 0;
        for (int v : next[u]) {
            res = (res + count(v, N - 1)) % M;
        }
        return m[u][N] = res;
    }

    int M = 1e9 + 7;
    vector<vector<int>> m, next;
};

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

173. Binary Search Tree Iterator 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
42
43
44
45
/**
 * 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:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        pushAllLeft(root1, s1);
        pushAllLeft(root2, s2);
        vector<int> res;
        while (!s1.empty() || !s2.empty()) {
            auto p = s1.empty() ? INT_MAX : s1.top()->val;
            auto q = s2.empty() ? INT_MAX : s2.top()->val;
            int mn = min(p, q);
            if (p == mn) {
                res.push_back(p);
                pushAllLeft(s1.top()->right, s1);
            }
            if (q == mn) {
                res.push_back(q);
                pushAllLeft(s2.top()->right, s2);
            }
        }
        return res;
    }

    void pushAllLeft(TreeNode *p, stack<TreeNode *> &s) {
        if (!s.empty()) { // 注意判空，因为一开始push的时候是空的
            s.pop();
        }
        while (p) {
            s.push(p);
            p = p->left;
        }
    }

    stack<TreeNode *> s1, s2;
};
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
/**
 * 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:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        pushAllLeft(root1, s1);
        pushAllLeft(root2, s2);
        vector<int> res;
        while (!s1.empty() || !s2.empty()) {
            auto p = s1.empty() ? nullptr : s1.top();
            auto q = s2.empty() ? nullptr : s2.top();
            if (p && q) {
                if (p->val <= q->val) {
                    res.push_back(p->val);
                    pushAllLeft(p->right, s1);
                } else {
                    res.push_back(q->val);
                    pushAllLeft(q->right, s2);
                }
            } else if (p) {
                res.push_back(p->val);
                pushAllLeft(p->right, s1);
            } else {
                res.push_back(q->val);
                pushAllLeft(q->right, s2);
            }
        }
        return res;
    }

    void pushAllLeft(TreeNode *p, stack<TreeNode *> &s) {
        if (!s.empty()) { // 注意判空，因为一开始push的时候是空的
            s.pop();
        }
        while (p) {
            s.push(p);
            p = p->left;
        }
    }

    stack<TreeNode *> s1, s2;
};

Posted on Edited on In Disqus:
Symbols count in article: 785 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
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int totalNQueens(int n) {
        this->n = n;
        total = 0;
        only_col.resize(n);
        row_minus_col.resize((n << 1) - 1);
        row_plus_col.resize((n << 1) - 1);
        totalNQueens_helper(0);
        return total;
    }

private:
    void totalNQueens_helper(int row) {
        if (row == n) {
            ++total;
            return;
        }
        for (int col(0); col < n; ++col) {
            if (!only_col[col] && !row_minus_col[n - 1 + row - col] && !row_plus_col[row + col]) {
                only_col[col] = row_minus_col[n - 1 + row - col] = row_plus_col[row + col] = true;
                totalNQueens_helper(row + 1);
                only_col[col] = row_minus_col[n - 1 + row - col] = row_plus_col[row + col] = false;
            }
        }
    }

    int total;
    int n;
    vector<bool> only_col;
    vector<bool> row_minus_col;
    vector<bool> row_plus_col;
};

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

backtracking O(n!) time O(n) space
There is N possibilities to put the first queen, not more than N * (N - 2) to put the second one, not more than N * (N - 2) * (N - 4) for the third one etc. In total that results in O(n!) time complexity.
按row去dfs，只需统计col以及两个方向的斜边即可

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<vector<string>> solveNQueens(int n) {
        this->n = n;
        chessboard.resize(n, string(n, '.'));
        only_col.resize(n);
        row_minus_col.resize((n << 1) - 1);
        row_plus_col.resize((n << 1) - 1);
        dfs(0);
        return res;
    }

private:
    void dfs(int r) {
        if (r == n) {
            res.push_back(chessboard);
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (!only_col[c]
                && !row_minus_col[n - 1 + r - c]
                && !row_plus_col[r + c]) {
                only_col[c] = row_minus_col[n - 1 + r - c] = row_plus_col[r + c] = true;
                chessboard[r][c] = 'Q';
                dfs(r + 1);
                chessboard[r][c] = '.';
                only_col[c] = row_minus_col[n - 1 + r - c] = row_plus_col[r + c] = false;
            }
        }
    }

    int n;
    vector<bool> only_col, row_minus_col, row_plus_col;
    vector<string> chessboard;
    vector<vector<string> > res;
};

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

hashtable版本 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(begin(nums), end(nums)); // 把所有数放到hashtable里
        int res = 0;
        for (int x : nums) {
            if (s.empty()) break;
            if (s.count(x - 1)) continue;
            int len = 0;
            while (s.count(x)) { // 从nums[i]开始找递增连续数列
                s.erase(x); // 每找到一个数就删除
                ++len;
                ++x;
            }
            res = max(res, len);
        }
        return res;
    }
};
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 longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end()); // 把所有数放到hashtable里
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n && !s.empty(); ++i) {
            int curr = nums[i];
            int len = 0;
            while (s.count(curr)) { // 从nums[i]开始找递增连续数列
                s.erase(curr);
                ++len;
                ++curr;
            }
            curr = nums[i] - 1; // 从nums[i] - 1开始找递减连续数列
            while (s.count(curr)) {
                s.erase(curr);
                ++len;
                --curr;
            }
            res = max(res, len);
        }
        return res;
    }
};

union-find 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        UF uf;
        for (int n : nums) {
            if (uf.has(n)) continue;
            uf.add(n);
            if (uf.has(n - 1)) {
                uf.merge(n - 1, n);
            }
            if (uf.has(n + 1)) {
                uf.merge(n + 1, n);
            }
        }
        return uf.mx;
    }

    struct UF {
        void add(int x) {
            parent[x] = x;
            size[x] = 1;
            mx = max(mx, 1);
        }

        bool has(int x) {
            return parent.find(x) != parent.end();
        }

        int getParent(int x) {
            while (parent[x] != parent[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;
                int sz = size[px] + size[py];
                size[px] = size[py] = sz;
                mx = max(mx, sz);
            }
        }

        unordered_map<int, int> parent, size;
        int mx = 0;
    };
};

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

dp + memo
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
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        n = days.size();
        cost.resize(n);
        vector<int> passes = {1, 7, 30};
        return mincost(0, days, 0, passes, costs); // lastDay从0开始，因为不知道days都是哪些天
    }

    int mincost(int lastDay, const vector<int> &days, int nextIdx, const vector<int> &passes, const vector<int> &costs) {
        if (nextIdx >= n) return 0;
        if (days[nextIdx] <= lastDay) return mincost(lastDay, days, nextIdx + 1, passes, costs); // 如果之前买的票可以cover当前这一天days[nextIdx]则继续测试days[nextIdx + 1]
        if (cost[nextIdx] > 0) return cost[nextIdx];
        int res = INT_MAX;
        for (int i = 0; i < 3; ++i) {
            res = min(res, mincost(days[nextIdx] + passes[i] - 1, days, nextIdx + 1, passes, costs) + costs[i]); // 分别测试三种票哪种可以使得总票价最低
        }
        return cost[nextIdx] = res;
    }

    int n;
    vector<int> cost; // cache
};