Mind palace

some thoughts

0%

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

hashmap O(n) time O(lvl) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthLongestPath(string input) {
        unordered_map<int, int> m{{-1, 0}}; // 加一个-1方便运算
        int res = 0;
        istringstream iss(input);
        string s;
        while (getline(iss, s)) { // 直接读一行
            int lvl = s.find_first_not_of('\t'); // 数tab个数即为层数
            m[lvl] = s.length() - lvl + m[lvl - 1]; // 当前层的长度-tab个数+上一层的累加和 即为 当前层的累加和
            if (s.find('.') != string::npos) { // 如果是一个文件的话
                res = max(res, m[lvl] + lvl); // 切记需要加上slash个数才是真的长度！！！
            }
        }
        return res;
    }
};

stack O(n) 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:
    int lengthLongestPath(string input) {
        if (input.empty()) return 0;
        int res = 0;
        stack<string> s;
        input += '\n';
        int b = 0, e = input.find('\n'), lvl = 0, len = 0;
        for (; e != string::npos; e = input.find('\n', b)) {
            while (s.size() > lvl) {
                len -= s.top().length();
                s.pop();
            }
            s.push(input.substr(b, e - b + 1));
            len += s.top().length();
            if (s.top().find('.') != string::npos) {
                res = max(res, len - 1);
            }
            for (b = e + 1, lvl = 0; b < input.length() && input[b] == '\t'; ++b, ++lvl);
        }
        return res;
    }
};

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

O(n) time O(n) space
这道题纯考实现
因为字符串形式的数不方便pop_back所以最好用int来表示数，确认没问题了再把数转成字符串

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<string> summaryRanges(vector<int>& nums) {
        vector<pair<int, int>> v;
        for (int x : nums) {
            if (v.empty() || v.back().second + 1 < x) {
                v.emplace_back(x, x);
            } else {
                v.back().second = x;
            }
        }
        vector<string> res;
        for (const auto &[b, e] : v) {
            if (b == e) {
                res.push_back(to_string(b));
            } else {
                res.push_back(to_string(b) + "->" + to_string(e));
            }
        }
        return res;
    }
};

O(n) time O(1) space
[res.back(), prev, x]

  1. res.back() < prev ===> “res.back() -> prev”
  2. res.back() == prev ===> “res.back()”即一个孤立的数
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> summaryRanges(vector<int>& nums) {
        vector<string> res;
        int n = nums.size();
        long prev = LONG_MIN; // 初始化prev表示前一个数
        for (int i = 0; i <= n; ++i) { // 因为需要处理最后一个数，所以延长到n
            long x = i == n ? LONG_MAX : nums[i]; // 取当前数
            if (prev + 1 < x) { // 如果不是连续的数
                if (!res.empty() && stoi(res.back()) < prev) { // append
                    res.back() += "->" + to_string(prev);
                }
                if (i < n) { // 把当前新起头的数存起来
                    res.push_back(to_string(x));
                }
            }
            prev = x;
        }
        return res;
    }
};

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

O(n) inorder traversal
维护一个中序遍历的当前最后一个节点lastNode，遍历完左子树，如果是valid，lastNode应该是左子树最后一个（最大的）节点，将其和root比较，如果比root小，则将lastNode更新为root然后遍历右子树，一个valid的BST必须始终保持lastNode是最大的节点且小于当前root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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 {
    TreeNode *lastNode = nullptr;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!isValidBST(root->left)) return false;
        if (lastNode && lastNode->val >= root->val) return false;
        lastNode = root;
        return isValidBST(root->right);
    }
};
Read more »

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

O(n2) time O(1) space
因为题目要求任何解法都可以，所以用最直白的思路，先从大到小找到每一个数，然后把这个数翻转到最开始，再翻转到对应的位置即可
类似bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        int n = A.size();
        vector<int> res;
        for (int i = n - 1; i >= 0; --i) {
            int k = distance(begin(A), find(begin(A), begin(A) + i + 1, i + 1));
            res.push_back(k + 1);
            reverse(begin(A), begin(A) + k + 1);
            res.push_back(i + 1);
            reverse(begin(A), begin(A) + i + 1);
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode dummy_head(0);
        dummy_head.next = head;
        auto slow = &dummy_head, fast = slow; // 如果希望最后slow落在(n - 1) / 2的那个，要从dummy_head开始
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        ListNode *prev = nullptr, *curr = fast;
        while (curr) {
            auto next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        fast = prev;
        slow = head;
        while (fast) {
            auto next = fast->next;
            fast->next = slow->next;
            slow->next = fast;
            slow = fast->next;
            fast = next;
        }
    }
};

O(n) 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode dummy_head(0);
        dummy_head.next = head;
        auto slow = &dummy_head, fast = slow;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        stack<ListNode *> s;
        while (fast) {
            s.push(fast);
            fast = fast->next;
        }
        slow = head;
        while (!s.empty()) {
            auto next = slow->next;
            s.top()->next = next;
            slow->next = s.top(); s.pop();
            slow = next;
        }
    }
};

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

hashmap+bucket sort O(n+k) worst case O(nlogn)
跟347. Top K Frequent Elements思路基本一样

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<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        int n = words.size();
        vector<set<string>> buckets(n + 1); // 因为要求按字典序排序所以复杂度会略高
        for (auto [w, freq] : m) {
            buckets[freq].insert(w);
        }
        vector<string> res;
        for (int i = n; i >= 0; --i) {
            for (const auto &w : buckets[i]) {
                res.push_back(w);
                if (size(res) == k) return res;
            }
        }
        return res;
    }
};

hashmap+trie+bucket sort O(n+k*w) time O(n) space w是平均字符长度

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
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        int n = words.size();
        vector<TrieNode *> buckets(n + 1, nullptr);
        for (auto&& b : buckets) {
            b = new TrieNode;
        }
        for (const auto &p : m) {
            insert(buckets[p.second], p.first);
        }
        vector<string> res;
        for (int i = n; i >= 0 && k > 0; --i) { // 题目要求高频到低频
            getWords(buckets[i], k, res);
        }
        return res;
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
        string w;
    };

    void insert(TrieNode *p, const string &w) {
        for (char c : w) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->isEnd = true;
        p->w = w;
    }

    void getWords(TrieNode *p, int &k, vector<string> &res) {
        if (!p || k == 0) return;
        if (p->isEnd) {
            res.push_back(p->w);
            --k;
        }
        for (int i = 0; i < 26; ++i) { // trie天然形成字典序
            getWords(p->children[i], k, res);
        }
    }
};

quickselect O(n+klogk) time worst case O(nlogn) O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        vector<pair<string, int>> v(begin(m), end(m));
        auto cmp = [](const auto &a, const auto &b){ return a.second == b.second ? a.first < b.first : a.second > b.second; };
        nth_element(begin(v), begin(v) + k, end(v), cmp);
        sort(begin(v), begin(v) + k, cmp);
        vector<string> res;
        for (const auto &[w, f] : v) {
            res.push_back(w);
            if (size(res) == k) return res;
        }
        return res;
    }
};

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

bfs O(n) 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
/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            res.push_back({});
            for (int i = size(q); i > 0; --i) {
                auto p = q.front(); q.pop();
                if (!p) continue;
                res.back().push_back(p->val);
                q.push(p->left);
                q.push(p->right);
            }
        }
        if (res.back().empty()) { // 别忘了最后要弹出空数组
            res.pop_back();
        }
        return res;
    }
};
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
/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<pair<TreeNode *, int>> q;
        q.emplace(root, 0);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first) {
                if (p.second < res.size()) res[p.second].push_back(p.first->val);
                else res.push_back({p.first->val});
                q.emplace(p.first->left, p.second + 1);
                q.emplace(p.first->right, p.second + 1);
            }
        }
        return res;
    }
};

preorder traversal O(n) time O(1) extra 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        preorder(root, res, 0);
        return res;
    }

    void preorder(TreeNode *root, vector<vector<int>> &res, int lvl) {
        if (!root) return;
        if (res.size() == lvl) {
            res.resize(lvl + 1);
        }
        res[lvl].push_back(root->val);
        preorder(root->left, res, lvl + 1);
        preorder(root->right, res, lvl + 1);
    }
};

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

postorder DFS O(n) serialize O(n) deserialize O(n) space
serialize时是左右中，deserialize的时候是中右左
digit转一字节字符+delimiter

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 Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return root ? serialize(root->left) + serialize(root->right) + to_string(root->val) + " " : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        int x;
        vector<int> v;
        while (input >> x) {
            v.push_back(x);
        }
        return insert(v, INT_MIN, INT_MAX);
    }

    // build BST
    TreeNode *insert(vector<int> &v, int mn, int mx) {
        if (v.empty() || v.back() < mn || v.back() > mx) return nullptr;
        auto root = new TreeNode(v.back());
        v.pop_back();
        root->right = insert(v, root->val, mx);
        root->left = insert(v, mn, root->val);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

int转4字节字符串，不需要delimiter

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return root ? serialize(root->left) + serialize(root->right) + toByte(root->val) : "";
    }

    string toByte(int x) {
        string res(4, 0);
        for (int i = 3; i >= 0; --i, x >>= 4) {
            res[i] = x & 15;
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<int> v;
        for (int i = 0; i < size(data); i += 4) {
            v.push_back(toInt(data, i));
        }
        return insert(v, INT_MIN, INT_MAX);
    }

    int toInt(const string &s, int b) {
        int res = s[b];
        for (int i = 1; i < 4; ++i) {
            res <<= 4; // 注意只左移3次！！
            res |= s[b + i];
        }
        return res;
    }

    // build BST
    TreeNode *insert(vector<int> &v, int mn, int mx) {
        if (v.empty() || v.back() < mn || v.back() > mx) return nullptr;
        auto root = new TreeNode(v.back());
        v.pop_back();
        root->right = insert(v, root->val, mx);
        root->left = insert(v, mn, root->val);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

去掉vector

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
63
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return root ? serialize(root->left) + serialize(root->right) + toByte(root->val) : "";
    }

    string toByte(int x) {
        string res(4, 0);
        for (int i = 3; i >= 0; --i, x >>= 4) {
            res[i] = x & 15;
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string_view sv{data};
        return insert(sv, INT_MIN, INT_MAX);
    }

    // int toInt(string_view sv) {
    //     int res = 0, n = size(sv);
    //     for (int i = 0, shift = 0; i < 4; ++i, shift += 4) {
    //         res |= (sv[n - i - 1] << shift);
    //     }
    //     return res;
    // }

    int toInt(string_view sv) {
        int res = 0;
        for (int i = 0, shift = 0; i < 4; ++i, shift += 4, sv.remove_suffix(1)) {
            res |= (sv.back() << shift);
        }
        return res;
    }

    // build BST
    TreeNode *insert(string_view &sv, int mn, int mx) {
        if (sv.empty()) return nullptr;
        int v = toInt(sv);
        if (v < mn || v > mx) return nullptr;
        sv.remove_suffix(4);
        auto root = new TreeNode(v);
        root->right = insert(sv, root->val, mx);
        root->left = insert(sv, mn, root->val);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

preorder DFS O(n) serialize O(nlogn) deserialize
前序遍历可以唯一确定bst的结构

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return root ? to_string(root->val) + " " + serialize(root->left) + serialize(root->right) : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string token;
        TreeNode dummy_root(INT_MIN); // 为了能让结果在右子树要选择INT_MIN
        while (input >> token) {
            insert(&dummy_root, stoi(token));
        }
        return dummy_root.right;
    }

    // build BST
    TreeNode *insert(TreeNode *root, int val) {
        if (!root) return root;
        if (val < root->val) {
            root->left = root->left ? insert(root->left, val) : new TreeNode(val);
        } else {
            root->right = root->right ? insert(root->right, val) : new TreeNode(val);
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return root ? to_string(root->val) + " " + serialize(root->left) + serialize(root->right) : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string token;
        TreeNode dummy_root(0);
        while (input >> token) {
            if (dummy_root.left) {
                insert(dummy_root.left, stoi(token));
            } else {
                dummy_root.left = new TreeNode(stoi(token));
            }
        }
        return dummy_root.left;
    }

        // build BST
    void insert(TreeNode *root, int val) {
        if (!root) return;
        if (val < root->val) {
            if (root->left) {
                insert(root->left, val);
            } else {
                root->left = new TreeNode(val);
            }
        } else {
            if (root->right) {
                insert(root->right, val);
            } else {
                root->right = new TreeNode(val);
            }
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

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

O(nlogn + n)
问贴海报需要几根钉子，扫描线做不了
贪心，先排序，只要左端升序即可，右端无所谓，因为始终维护右端最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(begin(points), end(points));
        int res = 0;
        long r = LONG_MIN; // 必须要用long，反例[INT_MIN, INT_MAX]
        for (const auto &v : points) {
            if (v[0] > r) {
                ++res;
                r = v[1]; // 因为要开启一个新的区间，所以直接使用这个区间的最右端
            } else {
                r = min(r, (long)v[1]);
            }
        }
        return res;
    }
};

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

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string reverseVowels(string s) {
        bool m[256] = {false};
        for (char v : "aeiouAEIOU") {
            m[v] = true;
        }
        int n = size(s), l = 0, r = n - 1;
        while (l < r) {
            while (l < r && !m[s[l]]) ++l;
            while (l < r && !m[s[r]]) --r;
            swap(s[l++], s[r--]);
        }
        return s;
    }
};