Mind palace

some thoughts

0%

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

decreasing stack O(n) time O(n) space
维护一个单调递减栈，栈里存下标，每次遇到更高的温度，对栈里的下标对应的结果进行更新后弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
                res[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }
        return res;
    }
};

从后往前维护一个单调递减栈，栈里存下标，每次判断当前下标和栈里第一个符合要求的下标的间距即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n);
        stack<int> s;
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
                s.pop();
            }
            res[i] = s.empty() ? 0 : (s.top() - i);
            s.push(i);
        }
        return res;
    }
};

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

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> res;
        for (int n = size(digits), i = n - 1, c = 0; i >= 0 || c > 0; --i) {
            int a = i >= 0 ? digits[i] : 0;
            int b = i == n - 1;
            int s = a + b + c;
            res.push_back(s % 10);
            c = s / 10;
        }
        return vector<int>(rbegin(res), rend(res));
    }
};

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

iterative O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr, *curr = head;
        while (curr) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};

recursive O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};

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

dp O(n) time O(n) space
跟爬楼梯那道题类似，每次只能爬一层或两层，问总共多少种爬法
最后一步：两个字符或者一个字符可以对应一个英文字母（但是要合法，两个字符要在10到26中间，一个字符不能为0）
子问题：f[i] = f[i - 1] + f[i - 2]
边界条件：f[0] = 1，即空串就只有一种decoding（这道题OJ有问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f[n + 1] = {1};
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1) {
                auto ret = stoi(s.substr(i - 2, 2));
                if (10 <= ret && ret <= 26) {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
};

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
class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f0 = 1, f1 = 1;
        for (int i = 1; i <= n; ++i) {
            int f2 = 0;
            if (s[i - 1] != '0') {
                f2 += f1;
            }
            if (i > 1) {
                auto x = stoi(s.substr(i - 2, 2));
                if (10 <= x && x <= 26) {
                    f2 += f0;
                }
            }
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
};
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 numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f0 = 1, f1 = 1;
        for (int i = 0; i < n; ++i) {
            int f2 = 0;
            if (s[i] != '0') {
                f2 += f1;
            }
            if (i > 0) {
                auto x = stoi(s.substr(i - 1, 2));
                if (10 <= x && x <= 26) {
                    f2 += f0;
                }
            }
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
};

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

bfs O(mn) time
先找到一个岛变成3同时找到岛的边缘海变成2
沿着边缘海扩张直到找到1为止
两个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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    int shortestBridge(vector<vector<int>>& A) {
        m = A.size(), n = A[0].size();
        auto [r, c] = getRC(A);
        int res = 0;
        auto &&q = update(A, r, c);
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                auto [r, c] = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int rr = r + dr[j], cc = c + dc[j];
                    if (!isValid(rr, cc)) continue;
                    if (A[rr][cc] == 0) {
                        q.emplace(rr, cc);
                        A[rr][cc] = 2;
                    } else if (A[rr][cc] == 1) return res;
                }
            }
        }
        return res;
    }

    pair<int, int> getRC(vector<vector<int>> &A) {
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (A[r][c] == 1) {
                    return {r, c};
                }
            }
        }
        return {0, 0};
    }

    queue<pair<int, int>> update(vector<vector<int>> &A, int r, int c) {
        queue<pair<int, int>> q{{{r, c}}}, res;
        A[r][c] = 3;
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (isValid(rr, cc)) {
                    if (A[rr][cc] == 1) {
                        q.emplace(rr, cc);
                        A[rr][cc] = 3;
                    } else if (A[rr][cc] == 0) {
                        res.emplace(rr, cc);
                        A[rr][cc] = 2;
                    }
                }
            }
        }
        return res;
    }

    bool isValid(int r, int c) {
        return 0 <= r && r < m && 0 <= c && c < n;
    }

    int m, n, dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
};

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

O(mn) time O(1) space
↘扫描一遍再↖扫描一遍，第一次扫可以得到到左上方land的最近距离，第二次扫可以得到到剩余land的最近距离，取最小值来更新全局最大值

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 maxDistance(vector<vector<int>>& grid) {
        int N = grid.size();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != 1) { // 注意是不为1，只有1是land
                    grid[i][j] = 200; // 所有water初始化为inf，这里用200防止后面overflow
                    if (i > 0) {
                        grid[i][j] = min(grid[i][j], grid[i - 1][j] + 1); // 向下propagate，要不是根据inf要不就是根据land
                    }
                    if (j > 0) {
                        grid[i][j] = min(grid[i][j], grid[i][j - 1] + 1); // 向右propagate
                    }
                }
            }
        }
        int res = 0;
        for (int i = N - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                if (grid[i][j] != 1) {
                    if (i + 1 < N) {
                        grid[i][j] = min(grid[i][j], grid[i + 1][j] + 1); // 向上propagate
                    }
                    if (j + 1 < N) {
                        grid[i][j] = min(grid[i][j], grid[i][j + 1] + 1); // 向左propagate
                    }
                    res = max(res, grid[i][j]);
                }
            }
        }
        return res % 200 - 1; // 最后结果要不是inf即200要不就是距离，最后要减1是因为从land开始propagate，land的值是1
    }
};

bfs O(mn) time O(min(m, 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        N = grid.size();
        queue<pair<int, int>> q;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) { // 横向扫每行找到边缘的land
                if (j > 0 && grid[i][j - 1] == 0 && grid[i][j] == 1) {
                    q.emplace(i, j);
                }
                if (j + 1 < N && grid[i][j] == 1 && grid[i][j + 1] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < N; ++i) { // 纵向扫每列找到边缘的land
                if (i > 0 && grid[i - 1][j] == 0 && grid[i][j] == 1) {
                    q.emplace(i, j);
                }
                if (i + 1 < N && grid[i][j] == 1 && grid[i + 1][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int res = -1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) { // bfs逐层扫描
                auto [r, c] = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int rr = r + dr[j], cc = c + dc[j];
                    if (isInBound(rr, cc) && grid[rr][cc] == 0) {
                        grid[rr][cc] = 2;
                        q.emplace(rr, cc);
                    }
                }
            }
            ++res;
        }
        return res;
    }

    bool isInBound(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    int N, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
};

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

分治 O(n) time O(1) space
这道题首先要统计字母频，突破口是字母频小于k的字母一定不在任何符合要求的子串里，即把整个字符串分割成若干『有可能符合要求』的子串，这样分而治之，对每个『有可能符合要求』的子串进行分析统计出最长的子串，因为每次分割都会至少去掉一个字母（如果有不符合要求的字母的话），所以最多需要26层，每层总计算步的和是O(n)，这样总的时间复杂度是O(26n)，即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
class Solution {
public:
    int longestSubstring(string s, int k) {
        return dfs(s, 0, size(s), k);
    }

    int dfs(const string &s, int b, int e, int k) {
        if (b == e || k > e - b) return 0; // 如果是空子串或者k过大
        if (k == 0) return e - b; // 如果k为0说明整个子串都是有效的
        int f[26] = {0};
        for (int i = b; i < e; ++i) {
            ++f[s[i] - 'a'];
        }
        int res = 0, p = b; // p表示可能的有效子串的开始下标
        for (int i = b; i <= e; ++i) {
            if (p == b && i == e) return e - b; // 如果整个子串都是有效的
            if (i == e || f[s[i] - 'a'] < k) { // 检查每一个可能的有效子串（包括最后一段，两个condition顺序不能颠倒，否则会越界）
                res = max(res, dfs(s, p, i, k));
                p = i + 1;
            }
        }
        return res;
    }
};
Read more »

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

merge sort O(nlogn) 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode dummy_head(0), *slow = &dummy_head, *fast = slow;
        dummy_head.next = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto l1 = head, l2 = slow->next;
        slow->next = nullptr;
        l1 = sortList(l1);
        l2 = sortList(l2);
        auto tail = &dummy_head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy_head.next;
    }
};

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

hashmap O(n) time
维护一个hashmap边扫边查边存

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (int i = 0, n = nums.size(); i < n; ++i) {
            if (m.count(nums[i]) && i - m[nums[i]] <= k) return true;
            m[nums[i]] = i;
        }
        return false;
    }
};

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

O(mn) 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        bool row0 = false, col0 = false; // row0和col0来标记第一行和第一列是否应该被设成0
        for (int c = 0; c < m; ++c) {
            if (matrix[0][c] == 0) {
                row0 = true;
                break;
            }
        }
        for (int r = 0; r < n; ++r) {
            if (matrix[r][0] == 0) {
                col0 = true;
                break;
            }
        }
        for (int r = 1; r < n; ++r) {
            for (int c = 1; c < m; ++c) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = matrix[0][c] = 0;
                }
            }
        }
        for (int r = 1; r < n; ++r) {
            for (int c = 1; c < m; ++c) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }
        if (row0) {
            for (int c = 0; c < m; ++c) {
                matrix[0][c] = 0;
            }
        }
        if (col0) {
            for (int r = 0; r < n; ++r) {
                matrix[r][0] = 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
32
33
34
35
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        bool col0 = false; // col0来标记第一列是否应该被设成0
        for (int r = 0; r < n; ++r) {
            if (matrix[r][0] == 0) {
                col0 = true;
            }
            for (int c = 1; c < m; ++c) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = matrix[0][c] = 0;
                }
            }
        }
        for (int r = 1; r < n; ++r) {
            for (int c = 1; c < m; ++c) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }
        if (matrix[0][0] == 0) {
            for (int c = 0; c < m; ++c) {
                matrix[0][c] = 0;
            }
        }
        if (col0) {
            for (int r = 0; r < n; ++r) {
                matrix[r][0] = 0;
            }
        }
    }
};