Mind palace

some thoughts

0%

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

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isStrobogrammatic(string num) {
        int m[] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        for (int n = num.length(), l = 0, r = n - 1; l <= r; ++l, --r) {
            int cl = num[l] - '0', cr = num[r] - '0';
            if (m[cl] == -1 || m[cr] == -1 || m[cl] != cr) return false;
        }
        return true;
    }
};

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

preorder 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
/**
 * 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 sumNumbers(TreeNode* root, int num = 0) {
        return sum(root, 0);
    }

private:
    long sum(TreeNode *root, long val) { // 返回这棵树所有Root to Leaf Numbers的和
        if (!root) return 0;
        val = val * 10 + root->val;
        if (!root->left && !root->right) return val; // 叶节点要单独处理
        return sum(root->left, val) + sum(root->right, val);
    }
};

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

O(mn) time O(1) space
类似merge的思路

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:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        int i = 0, j = 0, k = 0, n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();
        vector<int> res;
        while (i < n1 && j < n2 && k < n3) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                res.push_back(arr1[i]);
            }
            int mn = min({arr1[i], arr2[j], arr3[k]}); // 因为当前的三个数不同所以找出最小的数并跳过
            if (mn == arr1[i]) {
                ++i;
            }
            if (mn == arr2[j]) {
                ++j;
            }
            if (mn == arr3[k]) {
                ++k;
            }
        }
        return res;
    }
};
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:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        int i = 0, j = 0, k = 0, n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();
        vector<int> res;
        while (i < n1 && j < n2 && k < n3) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) { // 如果三个数都一样则输出
                res.push_back(arr1[i]);
                ++i;
                ++j;
                ++k;
            } else if (arr1[i] < arr2[j]) { // 如果arr1[i]不是最大则看arr1[i + 1]
                ++i;
            } else if (arr2[j] < arr3[k]) { // 如果arr2[j]不是最大则看arr2[j + 1]
                ++j;
            } else { // 如果arr3[k]不是最大则看arr3[k + 1]
                ++k;
            }
        }
        return res;
    }
};

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        unordered_map<int, int> m;
        for (int x : arr1) {
            ++m[x];
        }
        unordered_map<int, int> t;
        for (int x : arr2) {
            if (m.count(x)) {
                if (--m[x] == 0) {
                    m.erase(x);
                }
                ++t[x];
            }
        }
        t.swap(m);
        t.clear();
        for (int x : arr3) {
            if (m.count(x)) {
                if (--m[x] == 0) {
                    m.erase(x);
                }
                ++t[x];
            }
        }
        t.swap(m);
        t.clear();
        vector<int> res;
        for (auto [k, v] : m) {
            for (int i = 0; i < v; ++i) {
                res.push_back(k);
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};

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

iterative bfs O(mn) 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
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int dc[] = {0, 0, -1, 1}, dr[] = {-1, 1, 0, 0};
        int n = grid.size(), m = grid[0].size();
        int res = 0;
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < m; ++c) {
                res = max(res, bfs(grid, r, c, dr, dc, n, m));
            }
        }
        return res;
    }

    int bfs(vector<vector<int>> &grid, int r, int c, int dr[], int dc[], int n, int m) {
        queue<pair<int, int>> q;
        q.emplace(r, c);
        int res = 0;
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            if (0 <= r && r < n && 0 <= c && c < m && grid[r][c]) {
                ++res;
                grid[r][c] = 0;
                for (int i = 0; i < 4; ++i) {
                    q.emplace(r + dr[i], c + dc[i]);
                }
            }
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 507 Reading time ≈ 1 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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(begin(nums), end(nums));
        n = nums.size();
        dfs(nums, 0);
        return res;
    }

    void dfs(const vector<int> &nums, int b) {
        res.push_back(v); // 每构造一个新结果就输出
        for (int i = b; i < n; ++i) {
            if (i > b && nums[i - 1] == nums[i]) continue; // 去重
            v.push_back(nums[i]);
            dfs(nums, i + 1);
            v.pop_back();
        }
    }

    int n;
    vector<int> v;
    vector<vector<int>> res;
};

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

O(n!) time

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res{{}};
        for (int x : nums) {
            for (int i = size(res) - 1; i >= 0; --i) { // 一定要用n，不能动态取值
                res.push_back(res[i]);
                res.back().push_back(x);
            }
        }
        return res;
    }
};

backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }

    void dfs(const vector<int> &A, int b) {
        res.push_back(v);
        for (int i = b; i < size(A); ++i) {
            v.push_back(A[i]);
            dfs(A, i + 1);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};

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

做辅助线（延长线）找镜面反射的规律，每个pq对经过约分之后再分别对2取模，因为012的出现都是交替的

1
2
3
4
2 1 2 1 2
_ 0 _ 0 _
2 1 2 1 2
s 0 _ 0 _

举例p = 3, q = 2可以化简成p = 1, q = 0结果是一样的
最后规律如下

1
2
3
4
p q res
0 1 2
1 1 1
1 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
class Solution {
public:
    int mirrorReflection(int p, int q) {
        int res[] = {0, 2, 0, 1};
        int g = gcd(p, q); // 先约分化简（C++17自带）
        p /= g; p %= 2;
        q /= g; q %= 2;
        return res[p * 2 + q];
    }

    int gcd(int a, int b) {
        while (b != 0) {
            a %= b;
            swap(a, b);
        }
        return a;
    }

    // int gcd(int a, int b) {
    //     while (b != 0) {
    //         int t = a % b;
    //         a = b;
    //         b = t;
    //     }
    //     return a;
    // }
};

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

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canPermutePalindrome(string s) {
        int f[128] = {0};
        int odd_cnt = 0;
        for (char c : s) {
            odd_cnt += ((++f[c] & 1) << 1) - 1; // 奇数++偶数--
        }
        return odd_cnt <= 1;
    }
};

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

用hash table提前把所有path存起来 遍历每个path 从后往前删文件名（相当于从subfolder向上找parent folder的path）如果parent folder的path在hash table里 证明这是一个subfolder应该remove 否则将一直找到根目录的path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        unordered_set<string_view> s(begin(folder), end(folder));
        vector<string> res;
        for (const auto &f : folder) {
            string_view v(f);
            do {
                v.remove_suffix(v.length() - v.find_last_of('/'));
            } while (!v.empty() && !s.count(v));
            if (v.empty()) {
                res.push_back(f);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        unordered_set<string_view> s(begin(folder), end(folder));
        vector<string> res;
        for (const auto &f : folder) {
            string_view v(f);
            while (!v.empty()) {
                while (v.back() != '/') {
                    v.remove_suffix(1);
                }
                v.remove_suffix(1);
                if (s.count(v)) break;
            }
            if (v.empty()) {
                res.push_back(f);
            }
        }
        return res;
    }
};

类似trie

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:
    vector<string> removeSubfolders(vector<string>& folder) {
        root = new Folder;
        for (const auto &path : folder) {
            add(path);
        }
        dfs(root);
        return res;
    }

    struct Folder {
        unordered_map<string, Folder *> subfolders;
        string path;
    };

    Folder *root;

    void add(const string &path) {
        auto p = root;
        istringstream input(path);
        string name;
        while (getline(input, name, '/')) {
            if (!p->subfolders.count(name)) {
                p->subfolders[name] = new Folder;
            }
            p = p->subfolders[name];
        }
        p->path = path;
    }

    void dfs(Folder *p) {
        if (!p->path.empty()) {
            res.push_back(p->path);
            return;
        }
        for (auto &[_, subfolder] : p->subfolders) {
            dfs(subfolder);
        }
    }

    vector<string> res;
};

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

O(n) time O(n) space
这道题的意思是一定要『一对』才remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string S) {
        string res;
        for (char c : S) {
            if (!res.empty() && res.back() == c) {
                res.pop_back();
            } else {
                res += c;
            }
        }
        return res;
    }
};