Mind palace

some thoughts

0%

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

O(n) time O(26) space
是159. Longest Substring with At Most Two Distinct Characters 的follow-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> m;
        int res = 0;
        int n = s.length();
        for (int l = 0, r = 0; r < n; ++r) {
            ++m[s[r]];
            while (m.size() > k) { // 注意k有可能为0
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
            res = max(res, r + 1 - l);
        }
        return res;
    }
};

lee的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if (k == 0) return 0;
        unordered_map<char, int> m;
        int res = 0, l = 0, r = 0;
        int n = s.length();
        for (; r < n; ++r) {
            ++m[s[r]];
            if (m.size() > k) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
        }
        return r - l;
    }
};

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

O(logn) time O(n) space
[1, 3]是频数，即构造成下标数组[0, 1, 1, 1]然后随机一个index
累加频数，构造频数和数组[1, 4]，这里最后一个4是所有频数的和，即数组[0, 1, 1, 1]的长度，随机以后得到一个下标，需要得到下标所对应的原数组的index，因为频数和数组是递增的，所以二分可得到对应的频数和位置，即为原频数数组的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    Solution(vector<int>& w) {
        v = w;
        partial_sum(begin(v), end(v), begin(v), plus<int>());
        srand(time(NULL));
    }

    int pickIndex() {
        return upper_bound(begin(v), end(v), rand() % v.back()) - begin(v);
    }

    vector<int> v;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */
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:
    Solution(vector<int>& w) {
        v = w;
        for (int i = 1; i < v.size(); ++i) {
            v[i] += v[i - 1];
        }
        srand((unsigned)time(NULL));
    }

    int pickIndex() {
        return lower_bound(begin(v), end(v), (rand() % v.back() + 1)) - begin(v); // 加1恢复成1-indexed
    }

    vector<int> v;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */
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:
    Solution(vector<int>& w) {
        int sum = 0;
        for (int x : w) {
            v.push_back(sum += x); // 累加频数
        }
        srand((unsigned)time(NULL));
    }

    int pickIndex() {
        return distance(begin(v), upper_bound(begin(v), end(v), rand() % v.back())); // 这里要用upper_bound因为rand出来的是0-indexed，而频数本身是1-indexed，用lower_bound会找错，举例[1, 4]rand % 4出来的是下标1，而不是频数1，upper_bound找到的是频数和4，而lower_bound找到的是错误的频数和1
    }

    vector<int> v;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

follow-up如果weight数组是mutable的
用线段树，因为需要前缀和，把二分查找前缀和的上界改成二分查找区间和的上界，只是这个区间和是从0开始的
update O(logn)
query O(logn)
pickIndex O(logn*logn)
需要注意update和pickIndex的比例，如果很少update也可以考虑普通前缀和来做这样update虽然是O(n)但是pickIndex是O(logn)

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 Solution {
public:
    Solution(vector<int>& w) {
        n = w.size();
        v.resize(n * 2);
        copy(begin(w), end(w), begin(v) + n);
        for (int i = n - 1; i > 0; --i) {
            v[i] = v[i * 2] + v[i * 2 + 1];
        }
        srand(time(NULL));
    }

    void update(int i, int val) {
        i += n;
        for (int d = val - v[i]; i > 0; i >>= 1) {
            v[i] += d;
        }
    }

    int query(int i) {
        int res = 0;
        for (int l = n, r = i + n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                res += v[l++];
            }
            if ((r & 1) == 0) {
                res += v[r--];
            }
        }
        return res;
    }

    int pickIndex() {
        int x = rand() % v[1], l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (query(m) <= x) { // <是找下界<=是找上界c
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    vector<int> v;
    int n;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

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

O(C) time O(C) space
normalize每个单词存到hashmap里

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<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back(move(v));
        }
        return res;
    }

    string norm(string s) { // 返回以ASCII码0为基准的字符串
        int offset = 26 - s[0]; // 不关心'a'，只关心每个字符和s[0]的offset
        for (auto &&c : s) {
            c = (c + offset) % 26;
        }
        return s;
    }
};
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<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back(move(v)); // 转成右值直接move过去避免copy
        }
        return res;
    }

    string norm(string s) { // 返回值并不需要是一个正常的纯英文可读字符串
        int offset = 26 + 'a' - s[0]; // 这里假设以ASCII码0为基准 最后所有的'a'都变成0
        for (auto &&c : s) {
            c = (c - 'a' + offset) % 26; // 减'a'以后以字符0为基准 实际上因为是Galois Field不减'a'也行 但是不好描述
        }
        return s;
    }
};
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:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<int>> m; // 存下标就行，最后整理再放字符串
        int n = strings.size();
        for (int i = 0; i < n; ++i) {
            m[norm(strings[i])].push_back(i);
        }
        vector<vector<string>> res;
        for (const auto &[_, v] : m) {
            res.push_back({});
            for (int i : v) {
                res.back().push_back(strings[i]);
            }
        }
        return res;
    }

    string norm(string s) {
        int offset = 26 + 'a' - s[0];
        for (char &c : s) {
            c = (c + offset) % 26;
        }
        return s;
    }
};
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
class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strings) {
            m[norm(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto &&[_, v] : m) {
            res.push_back({});
            res.back().swap(v);
        }
        return res;
    }

    string norm(string s) { // 输出以'a'为基准的真正可读字符串
        int offset = 'a' - s[0];
        for (auto &&c : s) {
            auto t = c + offset;
            if (t < 'a') {
                c = 'a' + (t - 'a') + 26;
            } else {
                c = t;
            }
        }
        return s;
    }
};

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

bfs O(n) time 给每个node一个伪下标并维护最小最大下标，最后利用最小下标来还原真实下标
必须自顶向下自左向右 dfs如果不维护行号会违反 bfs完美符合不用维护行号只需要把每个数放到对应column即可所以选择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
/**
 * 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>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        vector<pair<int, TreeNode *>> v;
        queue<pair<int, TreeNode *>> q;
        q.emplace(0, root);
        int mn = INT_MAX, mx = INT_MIN;
        while (!q.empty()) {
            auto [idx, x] = q.front(); q.pop();
            v.emplace_back(idx, x);
            mn = min(mn, idx);
            mx = max(mx, idx);
            if (x->left) {
                q.emplace(idx - 1, x->left);
            }
            if (x->right) {
                q.emplace(idx + 1, x->right);
            }
        }
        vector<vector<int>> res(mx - mn + 1); // 利用最大最小下标提前分配内存
        for (auto [idx, x] : v) {
            res[idx - mn].push_back(x->val);
        }
        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
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        unordered_map<int, vector<TreeNode *>> m;
        queue<pair<int, TreeNode *>> q;
        q.emplace(0, root);
        int mn = INT_MAX, mx = INT_MIN;
        while (!q.empty()) {
            auto p = q.front(); q.pop();
            int idx = p.first;
            auto x = p.second;
            m[idx].push_back(x);
            mn = min(mn, idx);
            mx = max(mx, idx);
            if (x->left) {
                q.emplace(idx - 1, x->left);
            }
            if (x->right) {
                q.emplace(idx + 1, x->right);
            }
        }
        vector<vector<int>> res(mx - mn + 1);
        for (int i = mn; i <= mx; ++i) {
            for (auto x : m[i]) {
                res[i - mn].push_back(x->val);
            }
        }
        return res;
    }
};

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

O(nlog(n/k)) time O(n) space
n是node数 k是column数 也是树的width
插入是O(n)
整理是O(k*(n/k)log(n/k)) = O(nlog(n/k))
跟314. Binary Tree Vertical Order Traversal的区别是要相同位置的数要按大小排序，所以排序优先级是左右上下大小，因此必须维护行号，理论上bfs和dfs均可，但dfs代码简单

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
/**
 * 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>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector<int>> res(mx - mn + 1);
        for (auto &&[i, v] : m) {
            sort(begin(v), end(v));
            for (const auto &[j, val] : v) {
                res[i - mn].push_back(val);
            }
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i].emplace_back(j, root->val);
        mn = min(mn, i);
        mx = max(mx, i);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    int mn = INT_MAX, mx = INT_MIN;
    unordered_map<int, vector<pair<int, int>>> m;
};

O(nlogn) time O(n) space
插入是O(nlogk) k是column数 也是树的width
整理是O(k*(n/k)log(n/k))
O(nlogk + k*(n/k)log(n/k)) = O(nlogk + nlog(n/k)) = O(nlog(k*(n/k))) = O(nlogn)

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
/**
 * 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>> verticalTraversal(TreeNode* root) {
        dfs(root, 1000, 0); // 宽度从1000开始，层数从0开始
        vector<vector<int>> res;
        int prev = INT_MIN;
        for (auto &&p : m) {
            int curr = p.first / 1000; // 宽度即结果数组的row
            if (prev != curr) {
                res.push_back({});
                prev = curr;
            }
            res.back().insert(end(res.back()), begin(p.second), end(p.second));
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i * 1000 + j].insert(root->val);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    map<int, set<int>> m; // 同一坐标的数按数大小来排序所以要用set
};

如果没有1000这个限制条件，则把一维map转换成二维map

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
/**
 * 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>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for (auto &&[k, s] : m) {
            res.push_back({}); // 对于同一列要按照从上到下的顺序输出，同一位置再按大小输出
            for (auto &&[_, v] : s) {
                res.back().insert(end(res.back()), begin(v), end(v));
            }
        }
        return res;
    }

    void dfs(TreeNode *root, int i, int j) {
        if (!root) return;
        m[i][j].insert(root->val);
        dfs(root->left, i - 1, j + 1); // 因为要保证自顶向下的顺序所以这里一定要+1不能-1
        dfs(root->right, i + 1, j + 1);
    }

    map<int, map<int, set<int>>> m;
};

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

exponential O(4n) 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
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        n = size(num);
        string s(n << 1, 0); // 开一个buffer来拼结果
        dfs(0, 0, s, 0, num, 0, target);
        return res;
    }

private:
    void dfs(long sum, long last_num, string &s, int len, const string &num, int b, const int target) { // sum是当前计算结果，last_num是当前expr的最后一项，s是当前buffer状态，len是当前buffer中的expr的有效长度，b是当前剩余未扫描的num字符串的起始下标
        if (sum == target && b == n) {
            res.push_back(s.substr(0, len));
        }
        int l = len; // 因为要在当前expr基础上加optr，记录添加的位置
        if (b != 0) { // 因为第一个数字之前不能有optr，之后的才要给optr挪一个位置
            ++len;
        }
        long curr_num = 0;
        for (int i = b; i < n; ++i) {
            s[len++] = num[i]; // 往buffer里写入数字
            curr_num = curr_num * 10 + num[i] - '0';
            if (b == 0) { // 第一个数字前无optr，直接进入下一层递归
                dfs(curr_num, curr_num, s, len, num, i + 1, target);
            } else { // 添加optr然后进入下一层递归
                s[l] = '+'; dfs(sum + curr_num, curr_num, s, len, num, i + 1, target);
                s[l] = '-'; dfs(sum - curr_num, -curr_num, s, len, num, i + 1, target);
                s[l] = '*'; dfs(sum - last_num + last_num * curr_num, last_num * curr_num, s, len, num, i + 1, target);
            }
            if (num[b] == '0') break; // 数字不能以0开始
        }
    }

    int n;
    vector<string> res;
};

exponential O(n * 4n) 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
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        dfs(0, 0, "", 0, num, target);
        return res;
    }

    void dfs(long sum, long last_num, const string &s, int b, const string &num, const int target) {
        if (sum == target && b == num.length()) {
            res.push_back(s);
        }
        string curr_s;
        long curr_num = 0; // 必须用long防止溢出
        for (int i = b; i < num.length(); ++i) {
            curr_s += num[i];
            curr_num = curr_num * 10 + num[i] - '0';
            if (b == 0) { // +3456-23-74+90是错的，第一个数字前不能有符号
                dfs(curr_num, curr_num, curr_s, i + 1, num, target);
            } else {
                dfs(sum + curr_num, curr_num, s + '+' + curr_s, i + 1, num, target);
                dfs(sum - curr_num, -curr_num, s + '-' + curr_s, i + 1, num, target);
                dfs(sum - last_num + last_num * curr_num, last_num * curr_num, s + '*' + curr_s, i + 1, num, target);
            }
            if (num[b] == '0') { // 数字不能以0开始，2534+034是错的
                break;
            }
        }
    }

    vector<string> res;
};

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

amortized O(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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        pushAllLeft(root);
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        auto node(s.top());
        s.pop();
        pushAllLeft(node->right);
        return node->val;
    }

private:
    void pushAllLeft(TreeNode *root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }

    stack<TreeNode *> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

preorder iterator

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

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        auto p = s.top(); s.pop();
        if (p->right) {
            s.push(p->right);
        }
        if (p->left) {
            s.push(p->left);
        }
        return p->val;
    }

    stack<TreeNode *> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

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

inorder dfs O(n) time O(h) space
维护一个prev用root更新prev，因为prev一直被更新，所以到最后prev就是tail，最后连接head和prev（即tail）即可

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

    Node() {}

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return root; // 注意这里必须提前判空，因为后边不好处理
        dfs(root);
        auto head = dummy_head.right;
        head->left = prev;
        prev->right = head;
        return head;
    }

    void dfs(Node *root) {
        if (!root) return;
        dfs(root->left);
        prev->right = root;
        root->left = prev;
        prev = root;
        dfs(root->right);
    }

    Node dummy_head, *prev = &dummy_head;
};

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

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
24
25
26
27
class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        stack<vector<int>> s;
        for (const auto &l : logs) {
            auto e = parse(l);
            if (e[1]) {
                int t = e[2] - s.top()[2] + 1; // 先计算最近一个线程的时间
                res[e[0]] += t; // 修改最近一个线程的时间
                s.pop();
                if (!s.empty()) { // 如果前面还有别的线程被阻塞
                    res[s.top()[0]] -= t; // 从那个线程上减去最近这个线程的运行时间
                    // s.top()[2] += t; 是错的因为只考虑了局部，这道题必须从全局考虑，所以应该直接处理对应线程的最终结果，两层以上的nested call就是错的
                }
            } else {
                s.push(e);
            }
        }
        return res;
    }

    vector<int> parse(const string &s) {
        int p1 = s.find(":"), p2 = s.find(":", p1 + 1);
        return {stoi(s.substr(0, p1)), s.substr(p1 + 1, p2 - p1 - 1) == "end", stoi(s.substr(p2 + 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
class Solution {
    struct Log {
        Log(const string &s) {
            istringstream input(s);
            string token;
            getline(input, token, ':');
            id = stoi(token);
            getline(input, e, ':');
            getline(input, token, ':');
            time = stoi(token);
        }
        int id;
        string e;
        int time;
    };
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        int sz = logs.size();
        stack<Log> s;
        for (const auto &log : logs) {
            Log curr(log);
            if (curr.e == "start") {
                s.push(curr);
            } else {
                Log prev = s.top();
                s.pop();
                int interval = curr.time + 1 - prev.time;
                res[prev.id] += interval;
                if (!s.empty()) { // 这里很重要，父函数的实际运行时间不包括子函数的运行时间
                    res[s.top().id] -= interval; // s.top()是父函数，因为每次统计函数运行时间都是直接累加，所以要把子函数的运行时间『先』减掉
                }
            }
        }
        return res;
    }
};

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

sliding window O(m+n) time O(1) space
跟30. Substring with Concatenation of All Words解法基本一样

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> findAnagrams(string s, string p) {
        int f[26] = {0};
        for (char c : p) {
            ++f[c - 'a'];
        }
        vector<int> res;
        for (int m = s.length(), n = p.length(), cnt = 0, i = 0; i < m; ++i) {
            if (--f[s[i] - 'a'] >= 0) {
                ++cnt;
            }
            if (i >= n && ++f[s[i - n] - 'a'] > 0) {
                --cnt;
            }
            if (cnt == n) {
                res.push_back(i - n + 1);
            }
        }
        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<int> findAnagrams(string s, string p) {
        vector<int> mp(26), mc(26);
        for (char c : p) {
            ++mp[c - 'a'];
        }
        vector<int> res;
        int m = p.length(), n = s.length();
        for (int i = 0; i < n; ++i) {
            ++mc[s[i] - 'a'];
            if (i >= m - 1) { // 从m - 1开始就进行判断，避免在结尾处理的麻烦
                if (mc == mp) {
                    res.push_back(i - m + 1);
                }
                --mc[s[i - m + 1] - 'a'];
            }
        }
        return res;
    }
};