Mind palace

some thoughts

0%

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

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int n = A.size(), store = 0;
        for (int i = 1; i < n; ++i) {
            int c = A[i - 1] > A[i] ? -1 : (A[i - 1] < A[i]); // -1表示递减 0表示相等 1表示递增
            if (c == 0) continue; // 相等则跳过
            if (store * c < 0) return false;
            store = c; // 只保存严格递增或递减
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int n = A.size(), isInc = -1; // -1表示还没遇到严格递增或递减
        for (int i = 1; i < n; ++i) {
            if (A[i] == A[i - 1]) continue; // 相邻两数相同则跳过
            if (isInc == -1) { // 第一次遇到严格递增或递减
                isInc = A[i] > A[i - 1];
            }
            if (isInc ^ (A[i - 1] < A[i])) return false; // 如果之前的趋势和现在不一样，注意异或的优先级
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        char trend = 0;
        for (int n = size(A), i = 1; i < n; ++i) {
            if (A[i - 1] == A[i]) continue; // 相邻两数相同则跳过
            if (trend == 0) { // 第一次遇到严格递增或递减
                trend = A[i] - A[i - 1];
            } else if ((trend ^ (A[i] - A[i - 1])) < 0) return false;
        }
        return true;
    }
};

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

O(t) time t是tasks的个数题解
先统计字符频数，然后从大到小排序，初始idle的个数是(最大频数 - 1) * n，因为只统计(最大频数 - 1)范围内的区间，比如输入是AAABBB2，则初始化为A__A__，而不是A__A__A__，然后要做的就是按照频数从大到小往idle的slot里面放字符，这里要放在区间范围内，所以要用min(m[i], mx)，即AB_AB_，否则变成AB_AB_B就不对了，所有频数大于0的字符都放完以后，如果还有idle的slot说明剩下的字符只能放在后面了，即AB_AB_AB，不能再往idle的slot里面放了，否则说明不需要idle的slot分隔也足以让字符按照要求间隔的放，比如输入AAABBBCCC2，输出应为ABCABCABC
假设task是AAABBCCDD，n = 2

1
2
3
A12
A12
A

变成

1
2
3
ABCD
ABCD
A

则所有idel slot都占满，结果就是task.size() = 9
假设task是AAABBB，n = 2

1
2
3
A12
A12
A

变成

1
2
3
AB2
AB2
AB

还剩2个idle slot，结果就是taks.size() + 2 = 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int m[26] = {0};
        for (char c : tasks) {
            ++m[c - 'A'];
        }
        sort(m, m + 26, greater<int>());
        int mx = m[0] - 1, idle_slots = mx * n;
        for (int i = 1; i < 26 && m[i] > 0 && idle_slots >= 0; ++i) {
            idle_slots -= min(m[i], mx); // idle_slots是有可能放不开的，也就是最后变成负数
        }
        return tasks.size() + max(idle_slots, 0); // 这里要取max是因为idle_slots有可能因为放不开而『过饱和』，也就是变成负数，最后要把这些『负数』加回来，比如AAABBBCCCDDD2，最后idle_slots因为D放不进去变成-2
    }
};

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

bisection O(logn) time O(1) space
在数组中找missing number的『下界』，找下界的好处是最后确定缺哪个数直接计算即可，比找上界省事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = size(nums), l = 0, r = n - 1;
        while (l < r) {
            int m = (l + 1 + r) / 2; // 找下界为了避免死循环要+1
            if (nums[m] - nums[0] - m < k) { // (nums[m] - nums[0]) - (m - 0)得到nums[0]和nums[m]中间缺了几个数，如果少于k个说明nums[m]可能是下界
                l = m;
            } else {
                r = m - 1;
            }
        }
        return nums[0] + l + k; // 从nums[0]开始出现了l个数缺k个数，即nums[l] + k - (nums[l] - nums[0] - l)，从nums[l]开始数第k - (nums[l] - nums[0] - l)个数
    }
};

二分遍历整个数组，找出missing element在数组中的上界
对于一个数nums[m]，如果nums[m] - nums[0] - m >= k，则所求的missing element小于nums[m]，nums[m]是一个备选上界，否则肯定大于nums[m]并且nums[m]一定不是一个上界
找到上界nums[l]以后，分情况讨论

  1. 如果nums[l]是一个真上界，则missing element在(nums[l - 1], nums[l])之间，即k - (nums[l - 1] - nums[0] - (l - 1)) = k + nums[0] + l - 1，即从nums[0]开始跳过数组内的l - 1个数后找出第k个缺失的数
  2. 如果nums[l]是一个假上界，即数组里所有数都要比所求的missing element小，则应为k - (nums[l] - nums[0] - l) = k + nums[0] + l，即从nums[0]开始跳过数组内的l个数后找出第k个缺失的数

综合起来为k + nums[0] + l - isValid(nums, l, k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size(), l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isValid(nums, m, k)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[0] + k + l - isValid(nums, l, k);
    }

    bool isValid(const vector<int> &nums, int m, int k) {
        return nums[m] - nums[0] - m >= k; // 说明nums[m]比较大，第k个missing的数可以在nums[m]之内，即nums[0], ..., nums[0] + m, ..., nums[m]，所以nums[m] - (nums[0] + m) >= k
    }

};

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

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
28
29
30
31
32
33
34
35
36
/**
 * 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:
    TreeNode* str2tree(string s) {
        s += '(';
        TreeNode dummy;
        stack<TreeNode *> stk{{&dummy}};
        for (int i = 0, j = 0, n = s.length(); i < n; ++i) {
            if (s[i] != '(' && s[i] != ')') continue;
            if (i > j) {
                auto x = new TreeNode(stoi(s.substr(j, i - j)));// 把i和j两个相邻括号之间的内容变成数
                if (stk.top()->left) {
                    stk.top()->right = x;
                } else {
                    stk.top()->left = x;
                }
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
            j = i + 1;
        }
        return dummy.left;
    }
};
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
/**
 * 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* str2tree(string s) {
        s += '('; // in case no parenthesis
        stack<TreeNode*> stk;
        TreeNode dummy_root(0);
        stk.push(&dummy_root);
        for (int b = 0, i = s.find_first_of("()"); i != string::npos; b = i + 1, i = s.find_first_of("()", b)) { // find_first_of search any match of the input chars
            TreeNode *x = nullptr;
            string num = s.substr(b, i - b);
            if (!num.empty()) { // num might be empty e.g. ))
                x = new TreeNode(stoi(num));
            }
            if (!stk.top()->left) {
                stk.top()->left = x;
            } else if (!stk.top()->right) { // must use else if to check right child to avoid overwrite e.g. 4(2(3)(1)), 3 and 1 are 2's children, )) creates a nullptr to try overwriting 1
                stk.top()->right = x;
            }
            if (x) {
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
        }
        return dummy_root.left;
    }
};
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:
    TreeNode* str2tree(string s) {
        stack<TreeNode*> stk;
        TreeNode dummy_root(0);
        stk.push(&dummy_root);
        string num;
        for (int n = s.length(), i = 0; i < n; ++i) {
            if (s[i] == '(') continue; // 可有可无
            while (i < n && (isdigit(s[i]) || s[i] == '-')) {
                num += s[i++];
            }
            TreeNode *x = nullptr;
            if (!num.empty()) {
                x = new TreeNode(stoi(num));
                --i;
                num.clear();
            }
            if (!stk.top()->left) {
                stk.top()->left = x;
            } else if (!stk.top()->right) {
                stk.top()->right = x;
            }
            if (x) {
                stk.push(x);
            }
            if (s[i] == ')') {
                stk.pop();
            }
        }
        return dummy_root.left;
    }
};

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

O(n) 想象成柱状图，每个字母频数是一个柱，先把t中的字母频数加上去，然后r指针遍历s每个字符（扩大窗口），先减小各个字母的频数，然后l指针再二次遍历每个字符（缩小窗口）同时增大各个字母的频数直到恢复为正

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:
    string minWindow(string s, string t) {
        int f[128] = {0};
        for (char c : t) {
            ++f[c];
        }
        int n = s.length(), m = t.length(), ll = -1, rr = n;
        for (int r = 0, l = 0, cnt = 0; r < n; ++r) {
            if (--f[s[r]] >= 0) { // 先扩大窗口右端
                ++cnt;
            }
            while (cnt == m) { // 如果当前窗口里包含T的所有字符
                if (r - l < rr - ll) { // 更新结果
                    ll = l;
                    rr = r;
                }
                if (++f[s[l++]] > 0) { // 缩小窗口左端看能不能找到更小的符合要求的窗口
                    --cnt;
                }
            }
        }
        return ll == -1 ? "" : s.substr(ll, rr + 1 - ll);
    }
};

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:
    string minWindow(string s, string t) {
        int smap[256] = {0}, tmap[256] = {0};
        for (const auto &c : t) {
            ++tmap[c];
        }
        string res;
        int n = s.length(), window = INT_MAX;
        for (int i = 0, j = i; i < n; ++i) {
            while (j < n && !contains(smap, tmap)) {
                ++smap[s[j++]];
            }
            if (contains(smap, tmap) && j - i < window) {
                window = j - i;
                res = s.substr(i, window);
            }
            --smap[s[i]];
        }
        return res;
    }

    bool contains(int smap[], int tmap[]) {
        for (int i = 0; i < 256; ++i) {
            if (smap[i] < tmap[i]) {
                return false;
            }
        }
        return true;
    }
};

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

O(m*n*b) time O(m*n) space
思路很直白 遍历每个房子 对每个房子bfs 累加每个空地到每个房子的距离 要找的是一个可以reach所有房子的空地（前提是房子少空地多，否则就要对每个空地bfs）
这道题最重要的corner case是有的房子reach不到所有的空地
下面这个方法比较tricky但是省空间且不需要最后的遍历

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
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return -1;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> s(m, vector<int>(n));
        int cnt = 0, res = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    res = bfs(s, grid, cnt--, i, j, m, n); // cnt其实就是房子的个数
                    if (res == INT_MAX) return -1; // 有任何一个房子不能reach到所有空地，直接返回-1
                }
            }
        }
        return res;
    }

    int bfs(vector<vector<int>> &s, vector<vector<int>> &grid, int cnt, int i, int j, int m, int n) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int d = 1, res = INT_MAX;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                auto [ui, uj] = q.front(); q.pop();
                for (int p = 0; p < 4; ++p) {
                    int vi = ui + di[p];
                    int vj = uj + dj[p];
                    if (0 <= vi && vi < m && 0 <= vj && vj < n && cnt == grid[vi][vj]) { // 只有当前空地的计数器等于之前遍历过的所有房子的个数才有可能对res进行更新，如果之前有某个房子不能reach到，则当前空地的计数器一定和cnt不等；如果当前房子是reach不到的则res也不会更新，因为res会被overwritten，所以如果有一个房子reach不到，那么res会被改成INT_MAX并且之后再遍历的所有房子都不会再更新res
                        grid[vi][vj] = cnt - 1;
                        s[vi][vj] += d;
                        q.emplace(vi, vj);
                        res = min(res, s[vi][vj]);
                    }
                }
            }
            ++d;
        }
        return res;
    }

    int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -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
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return -1;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> s(m, vector<int>(n)), cnt = s; // s用来累加每个空地到其他房子的距离，cnt用来统计每个空地能有多少个房子reach
        int color = 0; // color用来给grid里的空地着色，避免重复访问
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    bfs(s, grid, cnt, --color, i, j, m, n);
                }
            }
        }
        int res = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s[i][j] > 0 && cnt[i][j] + color == 0) { // 如果存在一个空地可以reach所有房子，s[i][j] > 0说明是空地，cnt[i][j] + color == 0说明可以reach所有房子
                    res = min(res, s[i][j]);
                }
            }
        }
        return res == INT_MAX ? -1 : res; // 如果不存在能reach所有房子的空地
    }

    void bfs(vector<vector<int>> &s, vector<vector<int>> &grid, vector<vector<int>> &cnt, int color, int i, int j, int m, int n) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int d = 1;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                auto u = q.front(); q.pop();
                for (int p = 0; p < 4; ++p) {
                    int vi = u.first + di[p];
                    int vj = u.second + dj[p];
                    if (0 <= vi && vi < m && 0 <= vj && vj < n && color < grid[vi][vj] && grid[vi][vj] < 1) {
                        grid[vi][vj] = color;
                        s[vi][vj] += d;
                        q.emplace(vi, vj);
                        ++cnt[vi][vj];
                    }
                }
            }
            ++d;
        }
    }

    int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -1};
};

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

着色法 O(V+E) time O(v) 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:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        colors.resize(n);
        for (int i = 0; i < n; ++i) {
            if (colors[i] == 0 && !dfs(graph, i, 1)) return false;
        }
        return true;
    }

    bool dfs(const vector<vector<int>> &graph, int node, int color) {
        if (colors[node] != 0) return colors[node] == color;
        colors[node] = color;
        for (int neighbor : graph[node]) {
            if (!dfs(graph, neighbor, -color)) return false;
        }
        return true;
    }

    vector<char> colors;
};

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

桶排序 O(n) time O(10) 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 maximumSwap(int num) {
        int last[10] = {0};
        auto s = to_string(num);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            last[s[i] - '0'] = i; // 记录所有数字最后出现的位置
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 9; j > s[i] - '0'; --j) {
                if (i < last[j]) { // 对于每个处于高位的数字，如果能找到一个比它大的在低位的数字，交换并返回
                    swap(s[i], s[last[j]]);
                    return stoi(s);
                }
            }
        }
        return num;
    }
};

桶排序 O(n) time O(n) space
0到9十个数字十个桶，扫描数字字符串，把每个数字出现的下标保存到对应数字的桶里
从9到0依次扫描桶，取出当前桶i最后一次出现的下标b[i].back()，然后扫描所有比当前桶对应的数字小的数字的桶j中的第一次出现的下标b[j].front()并找到最小的下标l，将其与桶i最后一次出现的下标b[i].back()，交换原字符串中的数字即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maximumSwap(int num) {
        vector<vector<int>> b(10);
        auto s = to_string(num);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            b[s[i] - '0'].push_back(i);
        }
        for (int i = 9; i >= 0; --i) {
            if (b[i].empty()) continue;
            int l = b[i].back();
            for (int j = i - 1; j >= 0; --j) {
                if (b[j].empty()) continue;
                l = min(l, b[j].front());
            }
            if (l < b[i].back()) {
                swap(s[l], s[b[i].back()]);
                break;
            }
        }
        return stoi(s);
    }
};

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

iterative O(h) 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
/**
 * 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 closestValue(TreeNode* root, double target) {
        int res = root->val;
        while (root) {
            if (fabs(root->val - target) < fabs(res - target)) {
                res = root->val;
            }
            root = root->val > target ? root->left : root->right;
        }
        return res;
    }
};

recursive O(h) 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
/**
 * 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 closestValue(TreeNode* root, double target) {
        res = root->val;
        dfs(root, target);
        return res;
    }

    void dfs(TreeNode *root, double target) {
        if (!root) return;
        if (fabs(root->val - target) < fabs(res - target)) {
            res = root->val;
        }
        root->val > target ? dfs(root->left, target) : dfs(root->right, target);
    }

    int 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
/**
 * 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 closestValue(TreeNode* root, double target) {
        res = root->val;
        dfs(root, target);
        return res;
    }

    void dfs(TreeNode *root, double target) {
        if (!root) return;
        if (fabs(root->val - target) < fabs(res - target)) {
            res = root->val;
        }
        dfs(root->left, target);
        dfs(root->right, target);
    }

    int res;
};

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

deque O(n) time O(n) space
先把equation拆成后边（x+y）和前边（x-y）之差，即(xj + yj) - (xi - yi)，对于每个(xj + yj)只需要知道前边最小的(xi - yi)即可，又因为有一个限制条件|xi - xj| <= k，说明需要用sliding window，参考239. Sliding Window Maximum用deque维护一个xi - yi的升序，每次先把不符合限制条件|xi - xj| <= k的i从前边剔除，然后计算结果，再插入j并在尾部剔除较大的不符合要求的下标以保持升序
另外要注意如果k过小，有可能没有结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int res = INT_MIN;
        deque<int> q;
        for (int n = size(points), i = 0; i < n; ++i) {
            while (!q.empty() && points[i][0] - points[q.front()][0] > k) {
                q.pop_front();
            }
            if (!q.empty()) {
                res = max(res, points[i][0] + points[i][1] - (points[q.front()][0] - points[q.front()][1])); // 注意这道题一定要先计算再push新数，因为i < j
            }
            while (!q.empty() && points[q.back()][0] - points[q.back()][1] >= points[i][0] - points[i][1]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        return res;
    }
};