Mind palace

some thoughts

0%

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

O(n) time O(1) space
followup for infinite stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, c0 = 0, c1 = 0;
        for (int x : nums) {
            if (x == 1) {
                ++c0;
                ++c1;
            } else {
                c1 = c0 + 1;
                c0 = 0;
            }
            res = max(res, c1);
        }
        return res;
    }
};

找最长的子数组最多只包含一个0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0;
        for (int l = 0, r = 0, cnt = 0, n = size(nums); r < n; ++r) {
            if (nums[r] == 0) {
                ++cnt;
            }
            while (cnt > 1) {
                if (nums[l] == 0) {
                    --cnt;
                }
                ++l;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

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

236. Lowest Common Ancestor of a Binary Tree的followup
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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        auto res = lca(root, p, q);
        return cnt == 2 ? res : nullptr;
    }

    TreeNode *lca(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return root;
        auto l = lca(root->left, p, q);
        auto r = lca(root->right, p, q);
        if (root == p || root == q) {
            ++cnt;
            return root;
        }
        if (l && r) return root;
        return l ? l : r;
    }

    int cnt = 0;
};
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
/**
 * 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 res = lca(root, p, q);
        return cnt == 2 ? res : nullptr;
    }

    TreeNode *lca(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return root;
        if (root == p || root == q) {
            if (++cnt == 2) return root;
        }
        auto l = lca(root->left, p, q);
        auto r = lca(root->right, p, q);
        if (cnt == 1) return root;
        if (l && r) return root;
        if (cnt == 2) return (root == p || root == q) ? root : (l ? l : r);
        return nullptr;
    }

    int cnt = 0;
};

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

RESTful API 设计规范（转）

该仓库整理了目前比较流行的 RESTful api 设计规范，为了方便讨论规范带来的问题及争议，现把该文档托管于 Github，欢迎大家补充！！

Table of Contents

Read more »

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

dp O(NL) time O(NL) space
这道题的建模应该先从如何生成一个播放列表入手，因为有K首歌之内不能重复这个限制条件，所以我们一定是要一首歌一首歌往播放列表里添加并且每次都要检查是否跟前K首歌重复，如果重复则选择另外一首歌，所以我们只考虑不重复的合法情况：

  1. 跟当前已生成的播放列表完全不重复，这样的歌就是所有还未选择过的歌
  2. 跟前K首歌不重复但是跟K首歌之前的歌有重复，这样的歌就是已经被选择过的播放列表中的歌但是并不在最近的K首歌里

假设dp[l][n]表示对于播放表的前l首歌，去除重复的歌曲后还剩下n首歌的方案数。（即使用n首歌来生成播放表的前l首歌）

那么需要return的答案便为：dp[L][N] (因为每首歌必须至少出现一次，故这L首歌去除重复后一定有N首歌)

对于dp[l][n]的求解，需要分类讨论：

  1. 播放表的第l首歌跟前面的(l - 1)首都不一样，则对于dp[l][n]，我们可以先使用(n - 1)首歌排好播放表的前(l - 1)首歌，然后从剩下的(N - (n - 1))首歌
    里面再任意取一首歌，放在第l个位置，即：
    dp[l][n] += dp[l - 1][n - 1] * (N - (n - 1))

  2. 播放表的第l首歌跟前面的(l - 1)首存在重复的，则对于dp[l][n]，我们可以先使用n首歌排好前面的(l - 1)首歌，然后因为保证任意两首相同的歌之间至
    少有k首不同的歌，故对于dp[l - 1][n]里面的方案，最后的k首歌一定不一样，故我们只需要选一首跟最后面的k首歌不一样的歌，放在第l个位置即可，即：
    dp[l][n] += dp[l - 1][n] * (n - k)

此题得解，时间复杂度:O(NL)
注意一开始的初始化：dp[0][0] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        int M = 1e9 + 7;
        vector<vector<long>> f(L + 1, vector<long>(N + 1));
        f[0][0] = 1;
        for (int l = 1; l <= L; ++l) {
            for (int n = 1; n <= N; ++n) {
                f[l][n] = (f[l][n] + f[l - 1][n - 1] * (N - (n - 1))) % M;
                f[l][n] = (f[l][n] + f[l - 1][n] * max(0, n - K)) % M;
            }
        }
        return f[L][N];
    }
};

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

O(n) time O(1) space
l和r分别表示无法匹配的左括号跟右括号的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minAddToMakeValid(string S) {
        int l = 0, r = 0;
        for (char c : S) {
            if (c == '(') {
                ++l;
            } else if (c == ')') { // 当前字符是右括号且左括号有余则可以进行匹配，用掉一个左括号，否则增加一个无法匹配的右括号
                l > 0 ? --l : ++r;
            }
        }
        return l + r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minAddToMakeValid(string S) {
        int debt = 0, balance = 0;
        for (char c : S) {
            balance += c == '(' ? 1 : -1;
            if (balance < 0) { // 如果balance为负，说明欠钱了，先赊账，让balance平衡，最后debt和balance一起算
                ++debt;
                ++balance;
            }
        }
        return debt + balance;
    }
};

stack O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<char> s;
        for (char c : S) {
            if (c == ')' && !s.empty() && s.top() == '(') {
                s.pop();
            } else {
                s.push(c);
            }
        }
        return s.size();
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2k 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
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int m = S.length(), n = T.length();
        int i = m - 1, j = n - 1;
        for (; i >= 0 || j >= 0; --i, --j) { // 有可能是["", "ab##"]
            resolve(S, i);
            resolve(T, j);
            if (i < 0 || j < 0 || S[i] != T[j]) break; // 只要有一点不符合要求就break
        }
        return i < 0 && j < 0; // 两个字符串都扫完，说明没有不匹配的字符
    }

    void resolve(const string &s, int &i) {
        for (int cnt = 0; i >= 0; --i) {
            cnt += s[i] == '#' ? 1 : -1; // 类似括号匹配
            if (cnt < 0) return;
        }
    }
};
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
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int m = S.length(), n = T.length();
        int i = m - 1, j = n - 1;
        for (; i >= 0 || j >= 0; --i, --j) { // 有可能是["", "ab##"]
            resolve(S, i);
            resolve(T, j);
            if (i < 0 || j < 0 || S[i] != T[j]) break; // 只要有一点不符合要求就break
        }
        return i < 0 && j < 0; // 两个字符串都扫完，说明没有不匹配的字符
    }

    void resolve(const string &s, int &i) {
        int cnt = 0;
        while (i >= 0 && s[i] == '#') { // 只要还能继续删就一直处理完
            while (i >= 0 && s[i] == '#') {
                ++cnt;
                --i;
            }
            while (i >= 0 && s[i] != '#' && cnt-- > 0) {
                --i;
            }
        }
    }
};
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:
    bool backspaceCompare(string S, string T) {
        while (!S.empty() || !T.empty()) { // 一定是或不能是与，反例["nzp#o#g", "b#nzp#o#g"]
            resolve(S);
            resolve(T); // resolve完之后要不是空，要不结尾不能是#
            if (S.empty() || T.empty() || S.back() != T.back()) break;
            S.pop_back(); // 因为已经判过空了，所以可以直接pop
            T.pop_back();
        }
        return S.empty() && T.empty();
    }

    void resolve(string &s) {
        int cnt = 0;
        while (!s.empty() && s.back() == '#') { // 一定要处理干净再返回，比如"a#b#" ==> ""而不是"a#"
            while (!s.empty() && s.back() == '#') {
                ++cnt; // 数一下结尾几个#
                s.pop_back();
            }
            while (!s.empty() && s.back() != '#' && cnt > 0) { // 按照#的个数pop结尾字符，直到#个数为0或者字符串为空为止
                s.pop_back();
                --cnt;
            }
        }
    }
};

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

O(mn) time
count cells and shared edges
res = 4 * cells - 2 * shared edges

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int cnt = 0, shared = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j]) {
                    ++cnt;
                    shared += (i > 0 && grid[i - 1][j]);
                    shared += (j > 0 && grid[i][j - 1]);
                }
            }
        }
        return 4 * cnt - shared * 2;
    }
};

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 islandPerimeter(vector<vector<int>>& grid) {
        int perimeter = 0;
        for (int row = 0; row < grid.size(); ++row) {
            for (int col = 0; col < grid[row].size(); ++col) {
                if (grid[row][col]) {
                    if (0 == row || 0 == grid[row - 1][col]) {
                        ++perimeter;
                    }
                    if (grid.size() == row + 1 || 0 == grid[row + 1][col]) {
                        ++perimeter;
                    }
                    if (0 == col || 0 == grid[row][col - 1]) {
                        ++perimeter;
                    }
                    if (grid[row].size() == col + 1 || 0 == grid[row][col + 1]) {
                        ++perimeter;
                    }
                }
            }
        }
        return perimeter;
    }
};

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

O(n) time O(n) space
树转图+bfs
跟742. Closest Leaf in a Binary Tree类似

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
/**
 * 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> distanceK(TreeNode* root, TreeNode* target, int K) {
        dfs(root);
        list<int> q{{target->val}};
        while (K-- > 0 && !q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int u = q.front(); q.pop_front();
                for (int v : g[u]) {
                    g[v].erase(u);
                    q.push_back(v);
                }
            }
        }
        return vector<int>(begin(q), end(q));
    }

    void dfs(TreeNode *root) {
        if (!root) return;
        if (root->left) {
            g[root->val].insert(root->left->val);
            g[root->left->val].insert(root->val);
        }
        if (root->right) {
            g[root->val].insert(root->right->val);
            g[root->right->val].insert(root->val);
        }
        dfs(root->left);
        dfs(root->right);
    }

    unordered_map<int, unordered_set<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
38
39
40
41
42
43
44
/**
 * 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> distanceK(TreeNode* root, TreeNode* target, int K) {
        dfs(root);
        unordered_set<int> s{target->val};
        list<int> q{{target->val}};
        while (K-- > 0 && !q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int x = q.front(); q.pop_front();
                for (int y : g[x]) {
                    if (s.count(y)) continue;
                    s.insert(y);
                    q.push_back(y);
                }
            }
        }
        return vector<int>(begin(q), end(q));
    }

    void dfs(TreeNode *root) {
        if (!root) return;
        if (root->left) {
            g[root->val].push_back(root->left->val);
            g[root->left->val].push_back(root->val);
        }
        if (root->right) {
            g[root->val].push_back(root->right->val);
            g[root->right->val].push_back(root->val);
        }
        dfs(root->left);
        dfs(root->right);
    }

    unordered_map<int, vector<int>> g; // 邻接表
};

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

dp O(n2) time O(n2) space
区间型dp
算一下s[0:n-1]的最长回文子序列长度f[0][n - 1]
n - f[0][n - 1]是不在最长回文子序列里的即要从原字符串删除的字符个数
最后要判断n - f[0][n - 1]是否不超过k

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:
    bool isValidPalindrome(string s, int k) {
        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] = 1 + (s[i] == s[i + 1]);
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0, j = i + len; j < n; ++i, ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                }
            }
        }
        return n - f[0][n - 1] <= k;
    }
};

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

bfs O(An) A是密码盘字母数，本题是10，n是密码盘个数，本题是4

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
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> cache(begin(deadends), end(deadends));
        if (cache.count("0000")) return -1;
        queue<string> q{{"0000"}};
        int res = 0;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto s = q.front(); q.pop();
                if (s == target) return res;
                for (auto &&c : s) {
                    auto t = c;
                    for (int i : {-1, 1}) {
                        c = '0' + (t - '0' + 10 + i) % 10;
                        if (!cache.count(s)) {
                            q.push(s);
                            cache.insert(s);
                        }
                    }
                    c = t;
                }
            }
            ++res;
        }
        return -1;
    }
};