Mind palace

some thoughts

0%

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

朴素eratosthenes筛数法
O(nloglogsqrt(n)) time
证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countPrimes(int n) {
        if (n < 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < n; ++i) {
            if (!isPrime[i]) continue; // 如果不是质数直接跳过
            for (int j = i * i; j < n; j += i) { // 要从i * i开始，因为i * 2到i * (i - 1)都已经筛过了
                isPrime[j] = false;
            }
        }
        return count(isPrime.begin(), isPrime.end(), true);
        // return count_if(isPrime.begin(), isPrime.end(), [](bool isPrime) { return isPrime; });
    }
};

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

一个栈，比两个栈节省一点空间

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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if (x <= mn) { // 当需要修改当前最小值时，把旧的最小值压栈，然后修改，这里必须包含等于mn的情况，否则pop时无法判断栈顶下面是否压栈的是旧的mn还是另外一个数
            s.push(mn); // 压栈旧的最小值
            mn = x; // 更新最小值
        }
        s.push(x);
    }

    void pop() {
        int t = s.top(); s.pop();
        if (t == mn) { // 当要出栈的数跟当前最小值一样时，下一个栈顶的数一定是一个旧的最小值，用这个旧的最小值来给mn赋值
            mn = s.top(); s.pop();
        }
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return mn;
    }

    stack<int> s;
    int mn = INT_MAX;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

两个栈，一个正常栈维护数，一个最小值栈维护当前的最小值

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 MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        s.push(x);
        m.push(m.empty() ? x : min(m.top(), x));
    }

    void pop() {
        s.pop();
        m.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return m.top();
    }

    stack<int> s;
    stack<int> m;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

min queue
单调deque，最省空间
amortized O(1) 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
class MinQueue {
public:
    /** initialize your data structure here. */
    MinQueue() {

    }

    void push(int x) {
        while (!m.empty() && m.back() > x) {
            m.pop_back();
        }
        m.push_back(x);
        q.push(x);
    }

    void pop() {
        if (!m.empty() && q.front() == m.front()) {
            m.pop_front();
        }
        q.pop();
    }

    int front() {
        return q.front();
    }

    int getMin() {
        return m.front();
    }

    queue<int> q;
    deque<int> m;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

利用232. Implement Queue using Stacks

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
struct Queue {
    void push(int x) {
        back.push(x);
    }

    int pop() {
        rearrange();
        return front.pop();
    }

    int getMin() {
        int res = INT_MAX;
        if (!front.empty()) {
            res = min(res, front.getMin());
        }
        if (!back.empty()) {
            res = min(res, back.getMin());
        }
        return res;
    }

    void rearrange() {
        if (front.empty()) {
            while (!back.empty()) {
                front.push(back.pop());
            }
        }
    }

    Stack back, front;
};

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

MST O((V+E)log(V+E)) time O(V) space
这道题首先应该想到是求MST，然后思考如何抽象每个点来构造MST，观察到pipes里每个点都是1-indexed，说明应该有一个点0，解法就是加一个virtual node 0，把每个点自己的weight放到和0连起来的边上，就构成了一棵完整的0-indexed的图，求这个图的MST即可

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
class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        vector<tuple<int, int, int>> edges;
        for (int i = 0; i < n; ++i) {
            edges.emplace_back(wells[i], 0, i + 1);
        }
        for (const auto &p : pipes) {
            edges.emplace_back(p[2], p[0], p[1]);
        }
        sort(begin(edges), end(edges));
        parent.resize(n + 1);
        iota(begin(parent), end(parent), 0);
        int res = 0;
        for (const auto &[w, u, v] : edges) {
            if (merge(u, v)) {
                res += w;
            }
        }
        return res;
    }

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

    bool merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }

    vector<int> parent;
};

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

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        char t[4];
        int i = 0, cnt = 0;
        do {
            cnt = read4(t);
            int j = 0;
            while (i < n && j < cnt) {
                buf[i++] = t[j++];
            }
        } while (i < n && cnt == 4); // 注意如果read4读出来的字符少于4个就终止
        return i;
    }
};

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        char t[4];
        int cnt = read4(t), i = 0, j = 0;
        if (cnt == 0) return 0;
        while (i < n && j < cnt) {
            buf[i++] = t[j++];
        }
        if (i == n) return n;
        return cnt + read(buf + cnt, n - cnt);
    }
};

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

dp O(N2K) time O(N2) space
千万不要理解成bfs！！！每走一步需要记录整个棋盘的状态，所以是dp

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:
    double knightProbability(int N, int K, int r, int c) {
        vector<vector<double>> f(N, vector<double>(N));
        f[r][c] = 1;
        int dr[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dc[] = {1, 2, 2, 1, -1, -2, -2 ,-1};
        while (K-- > 0) { // 每走一步，重绘棋盘
            vector<vector<double>> t(N, vector<double>(N));
            for (int r = 0; r < N; ++r) {
                for (int c = 0; c < N; ++c) {
                    if (f[r][c] < 1e-8) continue; // 浮点数，不要直接跟0比
                    for (int i = 0; i < 8; ++i) {
                        int rr = r + dr[i], cc= c + dc[i];
                        if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
                        t[rr][cc] += f[r][c] * 0.125; // 累加当前位置出现queen的概率
                    }
                }
            }
            t.swap(f);
        }
        double res = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                res += f[r][c]; // 累加当前棋盘所有位置queen出现的概率和
            }
        }
        return res;
    }
};

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

这道题跟76. Minimum Window Substring不一样，那个题是找anagram，不需要保持顺序，这个需要
O(mn) time O(mn) space
把S的每个字符的位置按顺序记录在对应的T的每个字符的bucket里，因为S里的子序列必须严格follow T的顺序所以T的每个bucket对应的下标必须严格递增，扫描所有的bucket将不合法的下标排除，每次扫完更新全局结果即可

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:
    string minWindow(string S, string T) {
        unordered_map<char, vector<int>> c2q;
        int m = S.length(), n = T.length();
        for (int i = 0; i < n; ++i) {
            c2q[T[i]].push_back(i);
        }
        vector<queue<int>> q(n);
        for (int i = 0; i < m; ++i) {
            if (c2q.count(S[i])) {
                for (int j : c2q[S[i]]) {
                    q[j].push(i);
                }
            }
        }
        if (q[0].empty()) return "";
        int l = -1, r = m;
        while (!q[0].empty()) {
            for (int i = 1; i < n; ++i) {
                while (!q[i].empty() && q[i - 1].front() >= q[i].front()) {
                    q[i].pop();
                }
                if (q[i].empty()) return l == -1 ? "" : S.substr(l, r + 1 - l); // 如果有任何一个bucket空了，说明S里不存在合法的子序列或者之前已找到的子序列已经最优
            }
            if (q[n - 1].front() - q[0].front() < r - l) {
                l = q[0].front();
                r = q[n - 1].front();
            }
            q[0].pop();
        }
        return S.substr(l, r + 1 - l);
    }
};

双指针 O(mn) time O(1) space
先正着扫找符合要求的子序列，再倒着扫找到最短的子序列，类似sliding window

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:
    string minWindow(string S, string T) {
        int b = -1, len = INT_MAX;
        for (int m = size(S), n = size(T), i = 0, j = 0; i < m;) {
            while (i < m && j < n) { // 正向在S里找到第一个包含T序列的子串
                if (S[i] == T[j]) ++j;
                ++i;
            }
            if (j == n) { // 如果找到
                int e = i; // 先记录当前尾下标
                --i; --j; // 回退两个指针
                while (i >= 0 && j >= 0) { // 倒着在当前子串里找最大的起始下标
                    if (S[i] == T[j]) --j;
                    --i;
                }
                ++i; ++j; // 修正指针得到最大起始下标
                if (e - i < len) { // 更新结果
                    len = e - i;
                    b = i;
                }
                ++i; // 别忘了找到了一个可能结果还要往前移动指针继续找
            }
        }
        return b == -1 ? "" : S.substr(b, len);
    }
};

dp O(mn) time O(mn) space
f[i][j]表示S的前i个字符里包括T的前j个字符的子序列的最大的起始下标
需要维护一个全局最小起始下标和全局最小子序列长度
如果S[i - 1] == T[j - 1]则f[i][j]直接继承f[i - 1][j - 1]否则f[i][j]继承f[i - 1][j]即S的前i - 2个字符里包括T的前j个字符的子序列的最大的起始下标

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:
    string minWindow(string S, string T) {
        int m = S.length(), n = T.length(), mn = m, b = -1;
        vector<vector<int>> f(m + 1, vector<int>(n + 1, -1));
        for (int i = 0; i <= m; ++i) { // S的前i个字符和T的前0个字符空串的最大起始下标即为i这样f[i][0] - i为0，即不存在这样的子序列
            f[i][0] = i;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                f[i][j] = S[i - 1] == T[j - 1] ? f[i - 1][j - 1] : f[i - 1][j];
            }
            if (f[i][n] != -1) { // 如果S的前i个字符包括整个T则进行更新
                if (i - f[i][n] < mn) {
                    mn = i - f[i][n];
                    b = f[i][n];
                }
            }
        }
        return b == -1 ? "" : S.substr(b, mn);
    }
};

dp O(mn) 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:
    string minWindow(string S, string T) {
        int m = S.length(), n = T.length(), mn = m, b = -1;
        vector<int> f(n + 1, -1);
        f[0] = 0;
        for (int i = 1; i <= m; ++i) {
            vector<int> t(n + 1, -1);
            t[0] = i;
            for (int j = 1; j <= min(i, n); ++j) {
                t[j] = S[i - 1] == T[j - 1] ? f[j - 1] : f[j];
            }
            t.swap(f);
            if (f[n] != -1) {
                if (i - f[n] < mn) {
                    mn = i - f[n];
                    b = f[n];
                }
            }
        }
        return b == -1 ? "" : S.substr(b, mn);
    }
};

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

bfs O(nm)

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 ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> s(begin(wordList), end(wordList));
        queue<string> q{{beginWord}};
        s.erase(beginWord); // 如果beginWord在字典里则将其删去
        int res = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto w = q.front(); q.pop();
                if (w == endWord) return res;
                for (char &c : w) {
                    auto t = c;
                    for (char x = 'a'; x <= 'z'; ++x) {
                        c = x;
                        if (!s.count(w) || t == x) continue;
                        s.erase(w);
                        q.push(w);
                    }
                    c = t;
                }
            }
            ++res;
        }
        return 0;
    }
};

bfs O(nm) 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
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        q.push(beginWord);
        int res = 0;
        while (!q.empty()) {
            ++res;
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                auto w = q.front();
                q.pop();
                if (w == endWord) return res;
                int m = wordList.size();
                for (int j = 0; j < m; ++j) {
                    while (j < m && isSimilar(w, wordList[j])) {
                        q.push(wordList[j]);
                        swap(wordList[j], wordList[m - 1]);
                        wordList.pop_back();
                        --m;
                    }
                }
            }
        }
        return 0;
    }

    bool isSimilar(const string &s1, const string &s2) {
        int cnt = 0;
        int n = s1.length();
        for (int i = 0; i < n; ++i) {
            cnt += (s1[i] != s2[i]);
            if (cnt > 1) break;
        }
        return cnt == 1;
    }
};

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

bfs O(mn) time O(mn) space
这道题不能用堆+爬坡的方法，因为不是有序的，也不能用堆+灌水的方法，因为左上和右下两边是无关的，灌水法要求从外往里，每一层必须是一致的
解法：把沿海的边分别入队列，bfs爬坡标记两个海分别可以到哪些点，最后两个海都能到的点即为所求

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
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> v1(m, vector<bool>(n)), v2 = v1;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        bfs(matrix, 0, 0, m, n, v1, dx, dy); // 对每个沿海可达的地方标记
        bfs(matrix, m - 1, n - 1, m, n, v2, dx, dy);
        vector<vector<int>> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (v1[i][j] && v2[i][j]) { // 如果被标记过两次，说明这个地方两个海都可达
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &matrix, int r, int c, int m, int n, vector<vector<bool>> &v, int dx[], int dy[]) {
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) { // 把沿海的两条边入队列
            q.emplace(i, c);
            v[i][c] = true;
        }
        for (int j = 0; j < n; ++j) {
            q.emplace(r, j);
            v[r][j] = true;
        }
        while (!q.empty()) {
            int y = q.front().first, x = q.front().second; q.pop();
            for (int i = 0; i < 4; ++i) {
                int yy = y + dy[i], xx = x + dx[i];
                if (0 <= yy && yy < m && 0 <= xx && xx < n && !v[yy][xx] && matrix[yy][xx] >= matrix[y][x]) { // 爬坡
                    q.emplace(yy, xx);
                    v[yy][xx] = true;
                }
            }
        }
    }
};

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

O(nlogn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        map<int, int> m;
        for (const auto &i : intervals) {
            ++m[i[0]];
            --m[i[1]];
        }
        int res = 0, cnt = 0;
        for (auto [_, c] : m) {
            res = max(res, cnt += c);
        }
        return res;
    }
};

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

O(n) time
因为没有括号，所以不需要递归
整体思路是用加减把算式分隔开，把连续的乘除集中处理，op表示前一步运算，c表示当前处理的运算，每次不管c是加减乘除哪种运算都用local来跟num进行op的运算并把局部结果保存在local里，如果c是乘除则local继续处理运算（连续的乘除运算），如果c是加减则可以进行分割，把当前的局部结果累加到global里

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 calculate(string s) {
        long global = 0, local = 0, num = 0;
        char op = '+';
        s += '+';
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c != ' ') {
                switch (op) {
                    case '+': local += num; break;
                    case '-': local -= num; break;
                    case '*': local *= num; break;
                    case '/': local /= num; break;
                }
                if (c == '+' || c == '-') {
                    global += local;
                    local = 0; // local归零并不会影响后边的计算，因为当前的c是加减，所以下一步运算一定是0+/-num并得到一个新的local，如果c是乘除则不修改local，因为下一步运算是乘除，local被用了要清零
                }
                op = c;
                num = 0; // num被用了要清零
            }
        }
        return global;
    }
};
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 calculate(string s) {
        int res = 0, opnd = 0;
        istringstream input('+' + s + '+'); // 开头结尾都要加+来触发输入和累加更新res
        char op;
        while (input >> op) {
            if (op == '+' || op == '-') {
                res += opnd;
                if (input >> opnd) {
                    opnd *= (44 - op); // +的ASCII码是43，-的ASCII码是45
                }
            } else {
                int opnd2;
                input >> opnd2;
                if (op == '*') {
                    opnd *= opnd2;
                } else {
                    opnd /= opnd2;
                }
            }
        }
        return res;
    }
};