Mind palace

some thoughts

0%

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

O(n) time O(h) space
单调递减栈，因为对于每一个数x，都要找从左开始第一个比它小的数y，x是y的右子

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* bstFromPreorder(vector<int>& preorder) {
        TreeNode dummy_root(INT_MAX);
        stack<TreeNode *> s({&dummy_root});
        for (int x : preorder) {
            auto n = new TreeNode(x);
            TreeNode *p = nullptr;
            while (s.top()->val < x) {
                p = s.top();
                s.pop();
            }
            if (p) {
                p->right = n;
            } else {
                s.top()->left = n;
            }
            s.push(n);
        }
        return dummy_root.left;
    }
};

recursive 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
/**
 * 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 i = 0;
    TreeNode* bstFromPreorder(vector<int>& A, int bound = INT_MAX) { // bound是当前返回的这棵树的最大值上限
        if (i == A.size() || A[i] >= bound) return nullptr; // 当处理到叶结点的子结点时A[i] > bound
        TreeNode* root = new TreeNode(A[i++]);
        root->left = bstFromPreorder(A, root->val);
        root->right = bstFromPreorder(A, bound);
        return root;
    }
};

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

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
/**
 * 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:
    double maximumAverageSubtree(TreeNode* root) {
        dfs(root);
        return res;
    }

    pair<int, int> dfs(TreeNode *root) {
        if (!root) return {0, 0};
        auto [ls, lc] = dfs(root->left);
        auto [rs, rc] = dfs(root->right);
        int s = root->val + ls + rs, c = 1 + lc + rc;
        res = max(res, double(s) / c);
        return {s, c};
    }

    double res = 0;
};

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

O(n) time O(h + to_delete) space
判断是否需要删除需要hashtable
如果需要删除必须『真』删除，采用重新赋左右子的值的方法来删除
如果当前root需要删除，则把左右子树遍历删除后的结果尝试加入森林，所以需要后序遍历
如果当前root不需要删除，则update左右子之后返回即可（注意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
/**
 * 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<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x : to_delete) {
            s.insert(x);
        }
        auto ret = del(root);
        if (ret) {
            res.push_back(ret);
        }
        return res;
    }

    TreeNode *del(TreeNode *root) {
        if (!root) return root;
        auto l = del(root->left), r = del(root->right);
        if (s.count(root->val)) {
            if (l) {
                res.push_back(l);
            }
            if (r) {
                res.push_back(r);
            }
            return nullptr;
        }
        root->left = l;
        root->right = r;
        return root;
    }

    vector<TreeNode *> res;
    unordered_set<int> s;
};
Read more »

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

O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string convertToTitle(int n) {
        string res;
        while (n) {
            res += 'A' + (--n) % 26;
            n /= 26;
        }
        return string(rbegin(res), rend(res));
    }
};

复杂度不是O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string convertToTitle(int n) {
        string res;
        while (n) {
            res = char('A' + (--n) % 26) + res; // 这里一定要--n不能n-1，反例26 --> Z不是AZ
            n /= 26;
        }
        return res;
    }
};

Posted on In Disqus:
Symbols count in article: 296 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
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int x : nums) {
            int i = abs(x) - 1;
            if (nums[i] < 0) {
                res.push_back(i + 1);
            } else {
                nums[i] = -nums[i];
            }
        }
        return res;
    }
};

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

O(n) time O(26) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minDeletions(string s) {
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        sort(f, f + 26, greater());
        int res = 0;
        for (int i = 1; i < 26 && f[i]; ++i) {
            if (f[i] >= f[i - 1]) { // 有可能出现多个频数一样的减完会比下一个频数小，比如"abcabc"
                int x = max(0, f[i - 1] - 1); // 有可能前一个频数已为0
                res += f[i] - x;
                f[i] = x;
            }
        }
        return res;
    }
};

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

O(nlogx) x是最大的分母

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:
    string fractionAddition(string expression) {
        istringstream input(expression);
        int a, b, n = 0, d = 1;
        char c;
        while (input >> a >> c >> b) { // 这个很牛逼！！！
            n = n * b + a * d;
            d *= b;
            int g = gcd(abs(n), d); // 注意n为负数和0的情况
            n /= g;
            d /= g;
        }
        return to_string(n) + "/" + to_string(d);
    }

    int gcd(int a, int b) { // 不需要分大小
        while (b > 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
};

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

trie的应用 构造函数 O(nm) n是单词个数 m是单词长度 查询函数 O(k) k是prefix+suffix长度 空间复杂度 O(nm^2) 因为每个单词都可以派生出m个单词 每个单词长度为m 共n个单词 就是nmm
这道题最tricky的地方是如何存单词
Consider the word ‘apple’. For each suffix of the word, we could insert that suffix, followed by ‘#’, followed by the word, all into the trie.

For example, we will insert ‘#apple’, ‘e#apple’, ‘le#apple’, ‘ple#apple’, ‘pple#apple’, ‘apple#apple’ into the trie. Then for a query like prefix = “ap”, suffix = “le”, we can find it by querying our trie for le#ap.

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
class WordFilter {
public:

    struct TrieNode {
        TrieNode *children[27] = {nullptr};
        bool isEnd = false;
        int weight = 0;
    };

    WordFilter(vector<string> words) {
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            auto t = words[i];
            int m = t.length();
            for (int j = m; j >= 0; --j) {
                add(root, t.substr(j) + "{" + words[i], i);
            }
        }
    }

    int f(string prefix, string suffix) {
        return search(root, suffix + "{" + prefix);
    }

    void add(TrieNode *root, const string &s, int weight) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p->weight = weight; // 因为是从前往后insert单词所以权重可以直接覆盖
            p = p->children[c - 'a'];
        }
        p->isEnd = true;
        p->weight = weight;
    }

    int search(TrieNode *root, const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) return -1;
            p = p->children[c - 'a'];
        }
        return p->weight;
    }

    TrieNode *root = new TrieNode;
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
Read more »

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

dfs 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
31
32
33
34
35
36
37
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        dfs(root);
        return res;
    }

    void dfs(Node *u) {
        if (!u) return;
        for (auto v : u->children) {
            dfs(v);
        }
        res.push_back(u->val);
    }

    vector<int> res;
};

iterative

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        stack<pair<Node *, bool>> s;
        s.emplace(root, false);
        while (!empty(s)) {
            auto [u, visited] = s.top(); s.pop();
            if (!u) continue;
            if (visited) {
                res.push_back(u->val);
                continue;
            }
            s.emplace(u, true);
            for (auto it = rbegin(u->children); it != rend(u->children); ++it) {
                s.emplace(*it, false);
            }
        }
        return res;
    }
};

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

dfs 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
31
32
33
34
35
36
37
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        dfs(root);
        return res;
    }

    void dfs(Node *u) {
        if (!u) return;
        res.push_back(u->val);
        for (auto v : u->children) {
            dfs(v);
        }
    }

    vector<int> res;
};

iterative

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        stack<pair<Node *, bool>> s;
        s.emplace(root, false);
        while (!empty(s)) {
            auto [u, visited] = s.top(); s.pop();
            if (!u) continue;
            if (visited) {
                res.push_back(u->val);
                continue;
            }
            for (auto it = rbegin(u->children); it != rend(u->children); ++it) {
                s.emplace(*it, false);
            }
            s.emplace(u, true);
        }
        return res;
    }
};