Mind palace

some thoughts

0%

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

O(n) time O(1) space
1->2->3->null变成1->1’->2->2’->3->3’->null
新节点的random = 老节点的random的next，即将老节点和老节点的random的关系赋给新节点和新节点的random
将新老节点分开即可
分三步：

  1. copy next
  2. redirect random
  3. split

切记2跟3不能混做，因为random可能往回指

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 Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        for (auto p = head; p; p = p->next->next) {
            p->next = new Node(p->val, p->next, nullptr);
        }
        for (auto p = head; p; p = p->next->next) {
            p->next->random = p->random ? p->random->next : nullptr; // 一定要注意判空！！
        }
        Node dummy_head(-1, nullptr, nullptr), *tail = &dummy_head;
        for (auto p = head; p; p = p->next) {
            tail->next = p->next;
            tail = tail->next;
            p->next = tail->next;
        }
        return dummy_head.next;
    }
};
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 singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        for (auto p = head; p; p = p->next->next) {
            auto n = new RandomListNode(p->label);
            n->next = p->next;
            p->next = n;
        }
        for (auto p = head; p; p = p->next->next) {
            p->next->random = p->random ? p->random->next : nullptr;
        }
        RandomListNode dummy_head(0), *tail = &dummy_head, *p = head;
        while (p) {
            tail->next = p->next;
            tail = tail->next;
            p->next = tail->next;
            p = tail->next;
        }
        return dummy_head.next;
    }
};
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 with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        for (auto curr = head; curr; curr = curr->next) {
            auto node = new RandomListNode(curr->label);
            node->next = curr->next;
            curr->next = node;
            curr = node;
        }

        for (auto curr = head; curr; curr = curr->next->next) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
        }

        RandomListNode dummy_head(0);
        dummy_head.next = head;
        for (auto curr = head, succ = &dummy_head; curr; curr = curr->next) {
            succ->next = curr->next;
            succ = succ->next;
            curr->next = succ->next;
        }
        return dummy_head.next;
    }
};

hashmap 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
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode *, RandomListNode *> m;
        for (auto p = head; p; p = p->next) {
            m[p] = new RandomListNode(p->label);
        }
        for (auto p = head; p; p = p->next) {
            m[p]->next = p->next ? m[p->next] : nullptr;
            m[p]->random = p->random ? m[p->random] : nullptr;
        }
        return head ? m[head] : nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode *, RandomListNode *> hm;
        for (auto node = head; node; node = node->next) {
            hm[node] = new RandomListNode(node->label);
        }
        for (const auto &p : hm) {
            if (p.first->next) hm[p.first]->next = hm[p.first->next];
            if (p.first->random) hm[p.first]->random = hm[p.first->random];
        }
        return hm[head];
    }
};

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

worst case O(n*sum{dict[i].length}) time
纯暴力
维护一个bold数组标明每个字符是否需要bold
和616. Add Bold Tag in String是同一道题

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:
    string boldWords(vector<string>& words, string S) {
        int n = size(S);
        vector<bool> bold(n);
        for (const auto &w : words) {
            int p = -1;
            while (true) {
                p = S.find(w, p + 1);
                if (p == -1) break;
                fill_n(begin(bold) + p, size(w), true);
            }
        }
        string res;
        for (int i = 0; i < n; ++i) {
            if (bold[i] && (i == 0 || !bold[i - 1])) {
                res += "<b>";
            }
            res += S[i];
            if (bold[i] && (i == n - 1 || !bold[i + 1])) {
                res += "</b>";
            }
        }
        return res;
    }
};

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

worst case O(n*sum{dict[i].length}) time
纯暴力
维护一个bold数组标明每个字符是否需要bold
和758. Bold Words in String是同一道题

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:
    string addBoldTag(string s, vector<string>& dict) {
        int n = size(s);
        vector<bool> bold(n);
        for (const auto &w : dict) {
            int p = -1;
            while (true) {
                p = s.find(w, p + 1);
                if (p == -1) break; // npos等于-1
                fill_n(begin(bold) + p, size(w), true);
            }
        }
        string res;
        for (int i = 0; i < n; ++i) {
            if (bold[i] && (i == 0 || !bold[i - 1])) {
                res += "<b>";
            }
            res += s[i];
            if (bold[i] && (i == n - 1 || !bold[i + 1])) {
                res += "</b>";
            }
        }
        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
class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = s.length();
        vector<bool> bold(n);
        for (const auto &w : dict) {
            int len = w.length(), p = -1;
            while (true) {
                p = s.find(w, p + 1);
                if (p == -1) break;
                for (int i = 0; i < len; ++i) {
                    bold[p + i] = true;
                }
            }
        }
        string res;
        for (int i = 0; i < n;) {
            if (bold[i]) {
                res += "<b>";
                while (i < n && bold[i]) {
                    res += s[i++];
                }
                res += "</b>";
            } else {
                while (i < n && !bold[i]) {
                    res += s[i++];
                }
            }
        }
        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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        root = new TrieNode;
        for (const auto &w : dict) {
            add(w);
        }
        for (int n = s.length(), r = 0; r < n; ++r) {
            add(search(s, r), r);
        }
        string res;
        for (int n = s.length(), i = 0; i < n; ++i) {
            if (!lst.empty()) {
                auto [l, r] = lst.front();
                if (i == l) {
                    res += "<b>";
                }
                if (i == r) {
                    res += s[i];
                    res += "</b>";
                    lst.pop_front();
                    continue;
                }
            }
            res += s[i];
        }
        return res;
    }

    struct TrieNode {
        unordered_map<char, TrieNode *> children;
        bool isEnd = false;
    };

    TrieNode *root = nullptr;

    void add(const string &s) {
        auto p = root;
        for (int n = s.length(), i = n - 1; i >= 0; --i) {
            if (!p->children.count(s[i])) {
                p->children[s[i]] = new TrieNode;
            }
            p = p->children[s[i]];
        }
        p->isEnd = true;
    }

    int search(const string &s, int r) {
        auto p = root;
        int l = r + 1;
        for (int i = r; i >= 0; --i) {
            if (!p->children.count(s[i])) break;
            p = p->children[s[i]];
            if (p->isEnd) {
                l = min(l, i);
            }
        }
        return l;
    }

    void add(int l, int r) {
        if (l > r) return;
        while (!lst.empty() && l <= lst.back().second + 1) {
            l = min(l, lst.back().first);
            lst.pop_back();
        }
        lst.emplace_back(l, r);
    }

    list<pair<int, int>> lst;
};

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

这道题的关键点是如何快速根据区域内任意一点得到整个区域的面积，并查集是一种方案，查询每个点都能返回该点所在区域的唯一的根，另外一种方案就是用dfs或者bfs对该区域统一标号（着色）并对不同区域用不同的标号（颜色）来区分，查询每个点都能返回该区域的标号（颜色）
dfs O(n2) time O(n2) 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
49
50
51
52
53
54
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        vector<int> areas(2); // areas表示不同颜色的岛屿面积，颜色从2开始
        int color = 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    areas.push_back(dfs(grid, i, j, color++)); // 用dfs对每个岛着色并统计面积记录下来
                }
            }
        }
        if (areas.size() == 3 && areas[2] == n * n) return areas[2]; // 如果整个grid就是一个岛，直接返回
        int res = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) { // 遍历每一个0，如果与某些岛相邻则累加其面积
                    unordered_set<int> s;
                    int sum = 1;
                    for (int k = 0; k < 4; ++k) {
                        int r = i + dr[k];
                        int c = j + dc[k];
                        if (isValid(r, c) && grid[r][c] > 1 && s.count(grid[r][c]) == 0) {
                            s.insert(grid[r][c]);
                            sum += areas[grid[r][c]];
                        }
                    }
                    res = max(res, sum);
                }
            }
        }
        return res;
    }

    int dfs(vector<vector<int>> &grid, int i, int j, int color) {
        grid[i][j] = color;
        int res = 1;
        for (int k = 0; k < 4; ++k) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (isValid(r, c) && grid[r][c] == 1) {
                res += dfs(grid, r, c, color);
            }
        }
        return res;
    }

    bool isValid(int i, int j) {
        return 0 <= i && i < n && 0 <= j && j < n;
    }

    int n, dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
};
Read more »

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

记忆化搜索 memo+dfs O(n22n) time O(2nn+W) space
worst case是每个prefix都能在字典里找着，比如[‘a’, ‘aa’, ‘aaa’, …]这种，每个长度为i的suffix可能有2i - 1个组成方法，每次递归需要O(n)，递归深度为O(n)，所以总复杂度为O(n*n*2n)
这道题不需要用trie，太麻烦！
因为字符串没法简单的做backtracking所以采用后缀式搜索来避免
cache的时候用下标做key即可

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:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> d(wordDict.begin(), wordDict.end());
        return dfs(s, 0, d);
    }

    vector<string> dfs(const string &s, int b, const unordered_set<string> &d) {
        if (cache.count(b)) return cache[b];
        int n = s.length();
        if (b == n) return {""}; // 切记要返回一个空串不能是空集！！
        string w;
        for (int i = b; i < n; ++i) {
            w += s[i];
            if (d.count(w)) {
                for (const auto &suffix : dfs(s, i + 1, d)) {
                    cache[b].push_back(suffix.empty() ? w : w + ' ' + suffix); // 注意suffix有可能是空串！！
                }
            }
        }
        return cache[b];
    }

    unordered_map<int, vector<string>> cache;
};

Posted on Edited on In Disqus:
Symbols count in article: 532 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
/**
 * 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 rangeSumBST(TreeNode* root, int L, int R) {
        if (!root) return 0;
        int res = L <= root->val && root->val <= R ? root->val : 0;
        if (root->val > L) { // 必须是大于L
            res += rangeSumBST(root->left, L, R);
        }
        if (root->val < R) {
            res += rangeSumBST(root->right, L, R);
        }
        return res;
    }
};

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

扫描线版本很清晰 O(nlogn) 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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        map<int, int> m; // 扫一遍输入intervals把start和end存到map里
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        vector<Interval> res;
        int cnt = 0;
        int b = 0;
        for (const auto &p : m) { // 扫一遍map并实时统计区间个数
            if (cnt == 0) { // 扫当前时刻之前如果区间为0，则当前时刻是区间的开始
                b = p.first;
            }
            cnt += p.second;
            if (cnt == 0) { // 扫当前时刻之后如果区间为0，则当前时刻是区间的结束
                res.push_back({b, p.first});
            }
        }
        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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        map<int, int> m;
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        int cnt = 0;
        int s = INT_MAX;
        vector<Interval> res;
        for (const auto &p : m) {
            s = min(s, p.first);
            cnt += p.second;
            if (cnt == 0) {
                res.emplace_back(s, p.first);
                s = INT_MAX;
            }
        }
        return res;
    }
};

greedy O(nlogn) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        vector<vector<int>> res{intervals[0]};
        for (const auto &i : intervals) {
            if (i[0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], i[1]);
            } else {
                res.push_back(i);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(begin(intervals), end(intervals));
        int n = intervals.size();
        vector<vector<int>> res{intervals[0]};
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        auto cmp = [](const Interval &lhs, const Interval &rhs) { return lhs.start < rhs.start; };
        sort(intervals.begin(), intervals.end(), cmp);
        vector<Interval> res;
        for (const auto &i : intervals) {
            if (!res.empty() && i.start <= res.back().end) {
                res.back().end = max(res.back().end, i.end);
            } else {
                res.push_back(i);
            }
        }
        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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        int n = intervals.size();
        if (n == 0) return {};
        sort(intervals.begin(), intervals.end(), [](const Interval &lhs, const Interval &rhs)
        { return lhs.start < rhs.start; }); // 切记不要加别的条件
        vector<Interval> res{intervals[0]};
        for (int i = 1; i < n; ++i) {
            if (res.back().end >= intervals[i].start) {
                res.back().end = max(res.back().end, intervals[i].end); // 这里一定要用max比如[1,4],[2,3]这个反例
            } else {
                res.push_back(intervals[i]);
            }
        }
        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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval &lhs, const Interval &rhs)
        { return lhs.start < rhs.start; });
        int n = intervals.size();
        intervals.push_back(Interval(INT_MAX, INT_MAX));
        vector<Interval> res;
        for (int i = 0; i < n;) {
            int s = intervals[i].start;
            int e = intervals[i].end;
            int j = i + 1;
            for (; j < n && e >= intervals[j].start; ++j) {
                e = max(e, intervals[j].end);
            }
            res.emplace_back(s, e);
            i = j;
        }
        return res;
    }
};

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

O(n+A2) time O(A) space
先统计每个年龄的频数，然后两两比较各个年龄
这个题里的第三个条件是没用的，因为第二个条件比第三个条件更严格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int m[121] = {0};
        for (int a : ages) {
            ++m[a];
        }
        int res = 0;
        for (int a = 1; a < 121; ++a) {
            if (m[a] == 0) continue; // 没有这个年龄的人，跳过看下一个
            for (int b = 1; b <= a; ++b) { // 这里b > a是不符合条件的，所以上限设成a就行
                if (m[b] == 0 || a >= 2 * b - 14) continue; // 如果b不符合条件则跳过看下一个
                res += m[a] * m[b]; // 如果a和b年龄符合条件则所有a年龄的人都可以request年龄b的人
                if (a == b) { // 如果a年龄和b年龄一样，则要减去自身，因为自己不能request自己
                    res -= m[a];
                }
            }
        }
        return res;
    }
};

O(nlogn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        sort(begin(ages), end(ages));
        vector<int> t;
        for (int a : ages) {
            t.push_back(2 * a - 14);
        }
        int res = 0, n = t.size();
        for (int i = 0; i < n; ++i) {
            auto it1 = upper_bound(begin(t), end(t), 2 * ages[i] - 14); // B <= A(2B-14 <= 2A-14)
            auto it = upper_bound(begin(t), it1, ages[i]); // A < 2 * B - 14
            res += max(0, int(distance(it, it1) - 1)); // 因为找B <= A时找的上界多算了一个B，所以要减1
        }
        return res;
    }
};

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

考点是如何优化空间跟时间
mxn * nxp => mxp
A[i][j] * t[j][k] 累加到 res[i][k]
思路是遍历A，对每个非零A[i][j]，进行上述累加操作
普通矩阵乘法则是以最后结果矩阵为遍历顺序做点积运算

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:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = size(A), n = size(B), p = size(B[0]);
        vector<vector<pair<int, int>>> t(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < p; ++j) {
                if (B[i][j]) {
                    t[i].emplace_back(j, B[i][j]);
                }
            }
        }
        vector<vector<int>> res(m, vector<int>(p));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 0) continue;
                for (auto [k, v] : t[j]) {
                    res[i][k] += A[i][j] * v;
                }
            }
        }
        return res;
    }
};

先把矩阵B变成邻接表C，记录每个元素的列号
因为res[i][j]是A的第i行和B的第j列的点积，所以只需要遍历矩阵A
将A[i][k]和C[k]（即原来B的第k行的所有非0元素）的每个元素相乘并累加到对应的res[i][j]上即可

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:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size(), n = B.size(), p = B[0].size();
        vector<vector<pair<int, int>>> C(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < p; ++j) {
                if (B[i][j] != 0) {
                    C[i].emplace_back(j, B[i][j]);
                }
            }
        }
        vector<vector<int>> res(m, vector<int>(p));
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < m; ++i) {
                if (A[i][k] != 0) {
                    for (auto [j, val] : C[k]) {
                        res[i][j] += A[i][k] * val; // res[i][j]A的第i行和B的第j列的点积
                    }
                }
            }
        }
        return res;
    }
};

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

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
25
/**
 * 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:
    // 在root为根的二叉树中找A,B的LCA:
    // 如果找到了就返回这个LCA
    // 如果只碰到A，就返回A
    // 如果只碰到B，就返回B
    // 如果都没有，就返回null
		// 这里默认树上一定有p和q，所以不一定要真的把p和q都找到，假设只找到了其中一个，没找到另一个，说明找到的这个就是lca，另一个一定在以找到的这个点为根的树上
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);
        if (l && r) return root;
        return l ? l : r;
    }
};
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 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode *res;
        lca(root, p, q, res);
        return res;
    }

    void lca(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode *&res) {
        if (!root || root == p || root == q) {
            res = root;
            return;
        }
        TreeNode *l, *r;
        lca(root->left, p, q, l);
        lca(root->right, p, q, r);
        if (!l) {
            res = r;
        } else if (!r) {
            res = l;
        } else {
            res = root;
        }
    }
};