Mind palace

some thoughts

0%

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

binary search O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isBadVersion(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

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

O(n) BFS
“1 2 3 # # 4 5 # # # # “

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
/**
 * 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) {
        string res;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            auto n = q.front(); q.pop();
            if (n) {
                res += to_string(n->val);
                q.push(n->left);
                q.push(n->right);
            } else {
                res += "#";
            }
            res += " ";
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        TreeNode dummy_root(0);
        queue<pair<bool, TreeNode *>> q{{{true, &dummy_root}}};
        string s;
        while (input >> s) {
            TreeNode *n = (s == "#" ? nullptr : new TreeNode(stoi(s)));
            if (q.front().first) {
                q.front().second->right = n;
                q.pop();
            } else {
                q.front().second->left = n;
                q.front().first = true;
            }
            if (n) { // 这里要检查是否是空指针，因为要对queue里的指针设左右子树，不能出现空指针
                q.emplace(false, n);
            }
        }
        return dummy_root.right;
    }
};

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

preorder dfs
“1 2 # # 3 4 # # 5 # # “

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 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);
        return deserialize(input);
    }

    TreeNode *deserialize(istringstream &input) {
        string s;
        if (input >> s) {
            if (s == "#") return nullptr;
            auto res = new TreeNode(stoi(s));
            res->left = deserialize(input);
            res->right = deserialize(input);
            return res;
        }
        return nullptr;
    }
};

// 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: 3.7k Reading time ≈ 3 mins.

union-find O(sum(AilogAi)) time O(sum(Ai)) space where Ai = accounts[i].length()
用一个hashmap维护email和其对应的accounts的下标i
当不同account有相同的email时，merge对应的两个下标
最后整理原来accounts每个下标对应的所有email以及name即可

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
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> m;
        int n = accounts.size();
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < accounts[i].size(); ++j) {
                if (m.count(accounts[i][j])) {
                    merge(m[accounts[i][j]], i);
                } else {
                    m[accounts[i][j]] = i;
                }
            }
        }
        vector<set<string>> v(n);
        for (const auto &[s, i] : m) {
            v[find(i)].insert(s); // 归并email
        }
        vector<vector<string>> res;
        for (int i = 0; i < n; ++i) {
            if (v[i].empty()) continue;
            res.push_back({accounts[i][0]}); // 归并email和name
            res.back().insert(end(res.back()), begin(v[i]), end(v[i]));
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        parent[find(x)] = find(y);
    }

    vector<int> parent;
};
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
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> email2id;
        unordered_map<string, string> email2name;
        UF uf;
        int id = 0;
        for (const auto &a : accounts) {
            if (a.size() > 1) {
                if (!email2id.count(a[1])) {
                    email2id[a[1]] = id++;
                    email2name[a[1]] = a[0];
                }
                uf.add(email2id[a[1]]);
                for (int i = 2; i < a.size(); ++i) {
                    if (!email2id.count(a[i])) {
                        email2id[a[i]] = id++;
                        email2name[a[i]] = a[0];
                    }
                    uf.add(email2id[a[i]]);
                    uf.merge(email2id[a[1]], email2id[a[i]]);
                }
            }
        }
        unordered_map<int, set<string>> m;
        for (const auto &p : email2id) {
            m[uf.getParent(email2id[p.first])].insert(p.first);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            res.push_back({email2name[*p.second.begin()]});
            res.back().insert(res.back().end(), p.second.begin(), p.second.end());
        }
        return res;
    }

    struct UF {
        void add(int x) {
            if (parent.count(x)) return;
            parent[x] = x;
        }

        int getParent(int x) {
            while (parent[x] != x) {
                x = parent[x] = parent[parent[x]];
            }
            return parent[x];
        }

        void merge(int x, int y) {
            parent[getParent(x)] = getParent(y);
        }

        unordered_map<int, int> parent;
    };
};
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
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, pair<string, set<string>>> m;
        UF uf;
        for (const auto &a : accounts) {
            if (a.size() > 1) {
                uf.add(a[1]);
                m[a[1]].first = a[0];
                for (int i = 2; i < a.size(); ++i) {
                    uf.add(a[i]);
                    m[a[i]].first = a[0];
                    uf.merge(a[1], a[i]);
                }
            }
        }
        for (const auto &p : m) {
            m[uf.getParent(p.first)].second.insert(p.first);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            if (!p.second.second.empty()) {
                res.push_back({p.second.first});
                res.back().insert(res.back().end(), p.second.second.begin(), p.second.second.end());
            }
        }
        return res;
    }

    struct UF {
        void add(const string &s) {
            if (parent.count(s)) return;
            parent[s] = s;
        }

        string getParent(string s) {
            while (parent[s] != s) {
                s = parent[s] = parent[parent[s]];
            }
            return parent[s];
        }

        void merge(const string &x, const string &y) {
            parent[getParent(x)] = getParent(y);
        }

        unordered_map<string, string> parent;
    };
};

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

同余 O(n) time O(n) space
a % k = c
(a + sum) % k = c
sum % k = 0
需要sum的数字个数大于1
和974. Subarray Sums Divisible by K不同，k有可能为0，所以必须给前缀和维护一个hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> m; // 利用一个map保存<前缀和余数, 下标>
        m[0] = -1; // 因为连续的子数组是从头开始的，则需要提前先保存一个余数0
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (k != 0) sum %= k; // k如果是0，跳过即可
            if (m.count(sum)) { // 如果map里没有当前余数，保存即可，否则检查是否相隔至少2个数
                 if (i - m[sum] > 1) return true; // 这个if不能跟上一层的merge！！！因为有可能有相邻的
            } else {
                m[sum] = i;
            }
        }
        return false;
    }
};

前缀和O(n2) 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
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1);
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        for (int len = 1; len <= n - 1; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                int sum = presum[j + 1] - presum[i];
                if (k == 0) {
                    if (sum == 0) return true;
                    continue;
                }
                if (sum / k * k == sum) return true;
            }
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 627 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 isPalindrome(string s) {
        for (int l = 0, r = s.length() - 1; l < r; ++l, --r) {
            while (l < r && !isalnum(s[l])) ++l;
            while (l < r && !isalnum(s[r])) --r;
            if (tolower(s[l]) != tolower(s[r])) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.length();
        int l = 0, r = n - 1;
        while (l < r) {
            while (l < r && !isalnum(s[l])) {
                ++l;
            }
            while (l < r && !isalnum(s[r])) {
                --r;
            }
            if (tolower(s[l]) != tolower(s[r])) return false; // uniform case!!
            ++l;
            --r;
        }
        return true;
    }
};

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

quickselect O(n) on avg

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        int n = nums.size(), l = 0, r = n - 1;
        while (l <= r) {
            int m = partition(nums, l, r);
            if (m == k - 1) return nums[m];
            if (m < k - 1) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    int partition(vector<int> &A, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(A[l], A[v[rand() % 3]]);
        int j = l + 1; // 从pivot下一个开始
        for (int i = j; i <= r; ++i) {
            if (A[i] > A[l]) {
                swap(A[i], A[j++]); // 凡是比pivot大的就往前换
            }
        }
        swap(A[--j], A[l]); // 拿最后一个比pivot大的跟pivot交换
        return 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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned)time(NULL));
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int i = partition(nums, l, r);
            if (i == k - 1) return nums[i];
            if (i > k - 1) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return -1;
    }

    int partition(vector<int> &nums, int l, int r) {
        vector<int> v{l, (l + r) / 2, r};
        swap(nums[l], nums[v[rand() % 3]]);
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] <= pivot) { // 因为是求第k大所以要降序
                --r;
            }
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot) {
                ++l;
            }
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};
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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int l = 0, r = n - 1; // 左右闭区间
        while (l <= r) { // 要考虑l == r的情况
            auto i = partition(nums, l, r);
            if (i == k - 1) { // k是从1开始的
                return nums[i];
            } else if (i < k - 1) {
                l = i + 1;
            } else {
                r = i - 1;
            }
        }
    }

    int partition(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        int l = left, r = right;
        while (l < r) {
            while (l < r && nums[r] <= pivot) --r;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot) ++l;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};

O(nlogk) 最小堆里永远保存k个数，堆顶的数是当前第k大的数，如果一个数比堆顶的数大，则入堆，堆自动调整后，将堆顶多余的第k+1大的数弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> h;
        for (const auto &n : nums) {
            if (h.size() < k) {
                h.push(n);
            } else if (h.top() < n) {
                h.pop();
                h.push(n);
            }
        }
        return h.top();
    }
};

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

1249. Minimum Remove to Make Valid Parentheses的followup
time worst case O(n2) “)a)a)a)a)a” 因为需要最后的结果

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
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        remove(s, 0, 0, '(', ')');
        return res;
    }

    void remove(const string &s, int sb, int rb, char lp, char rp) {
        if (int i = search(s, sb, lp, rp); i == s.length()) {
            string t(rbegin(s), rend(s));
            if (lp == '(') {
                remove(t, 0, 0, rp, lp);
            } else {
                res.push_back(t);
            }
        } else {
            for (int j = rb; j <= i; ++j) {
                if (s[j] == rp && (j == rb || s[j] != s[j - 1])) {
                    remove(s.substr(0, j) + s.substr(j + 1), i, j, lp, rp);
                }
            }
        }
    }

    int search(const string &s, int b, char lp, char rp) { // 找到第一个不匹配的右括号
        int i = b;
        for (int cnt = 0; i < s.length(); ++i) {
            cnt += (s[i] == rp) ? -1 : (s[i] == lp);
            if (cnt < 0) break;
        }
        return i;
    }

    vector<string> 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:
    vector<string> removeInvalidParentheses(string s) {
        remove(s, 0, 0, '(', ')');
        return res;
    }

    void remove(const string &s, int sb, int rb, char lp, char rp) {
        int i = sb, cnt = 0;
        while (i < s.length() && cnt >= 0) { // 遍历字符串直到找到第一个匹配不上的『右括号』
            cnt += (s[i] == rp ? -1 : s[i] == lp); // 注意字符串里可能还有非左右括号的字符
            ++i;
        }
        if (cnt >= 0) { // 如果没有匹配不上的『右括号』则翻转字符串尝试删除匹配不上的『左括号』
            string t(rbegin(s), rend(s));
            if (lp == '(') {
                remove(t, 0, 0, rp, lp);
            } else { // 如果两种case都已经尝试过了，则当前字符串已经全部匹配
                res.push_back(t);
            }
        } else { // 当找到第一个匹配不上的『右括号』
            --i; // 先回退到这个匹配不上的『右括号』
            for (int j = rb; j <= i; ++j) { // 从上次删除过的位置开始一直到当前这个匹配不上的为止，尝试删除『右括号』并拼成新字符串
                if (s[j] == rp && (j == rb || s[j - 1] != s[j])) { // 跳过连续『右括号』去重
                    remove(s.substr(0, j) + s.substr(j + 1), i, j, lp, rp); // 下个iteration的删除要从这次删除的位置j开始
                }
            }
        }
    }

    vector<string> res;
};

O(2n) 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
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (char c : s) { // 先统计需要删除几个左括号和右括号（无法匹配）
            if (c == '(') {
                ++l;
            } else if (c == ')') {
                l > 0 ? --l : ++r;
            }
        }
        helper(s, 0, l, r);
        return res;
    }

private:
    void helper(string s, int b, int l, int r) {
        if (l == 0 && r == 0) { // 如果多余的左括号和右括号都已经删除
            if (isValid(s)) // 判断当前的字符串是否合法（因为是盲删的所以可能得到的字符串不合法）
                res.push_back(s);
            return;
        }
        for (int i = b; i < s.length(); ++i) {
            if (i > b && s[i - 1] == s[i]) continue; // 去重，比如连续两个右括号，删一个即可
            if (s[i] == '(' && l > 0) { // 盲删左括号
                helper(s.substr(0, i) + s.substr(i + 1), i, l - 1, r); // 从i开始也是一种去重
            } else if (s[i] == ')' && r > 0) { // 盲删右括号
                helper(s.substr(0, i) + s.substr(i + 1), i, l, r - 1); // 切记不要用s.erase因为是循环删除，所以前面删除以后会影响后边
            }
        }
    }

    bool isValid(string s) {
        int cnt = 0;
        for (char c : s) {
            if (c == '(') {
                ++cnt;
            } else if (c == ')') {
                if (--cnt < 0) return false;
            }
        }
        return cnt == 0;
    }

    vector<string> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins. 
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
class WordDictionary {
    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
    };

    TrieNode *root = nullptr;

public:
    /** Initialize your data structure here. */
    WordDictionary() : root(new TrieNode) {

    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        auto p = root;
        for (auto c : word) {
            int k = c - 'a';
            if (!p->children[k]) {
                p->children[k] = new TrieNode;
            }
            p = p->children[k];
        }
        p->isEnd = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return search(word, 0, root);
    }

    bool search(const string &w, int i, TrieNode *p) {
        if (!p) return false;
        if (i == w.length()) return p->isEnd;
        if (w[i] != '.') return search(w, i + 1, p->children[w[i] - 'a']);
        for (int k = 0; k < 26; ++k) {
            if (search(w, i + 1, p->children[k])) return true;
        }
        return false;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

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

hash table 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
24
25
26
27
28
29
class SparseVector {
public:

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                m[i] = nums[i];
            }
        }
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (const auto &[i, v] : vec.m) {
            if (m.count(i)) {
                res += m[i] * vec.m[i];
            }
        }
        return res;
    }

    unordered_map<int, int> m;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

常规拉链法
O(m+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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class SparseVector {
public:

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                v.emplace_back(i, nums[i]);
            }
        }
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (int i = 0, j = 0, m = getDim(), n = vec.getDim(); i < m && j < n;) {
            int ii = getIdx(i), ij = vec.getIdx(j);
            if (ii == ij) {
                res += getNum(i++) * vec.getNum(j++);
            } else if (ii < ij) {
                ++i;
            } else {
                ++j;
            }
        }
        return res;
    }

    int getIdx(int i) {
        return v[i].first;
    }

    int getNum(int i) {
        return v[i].second;
    }

    int getDim() {
        return v.size();
    }

    vector<pair<int, int>> v;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

二分拉链 worst case O(mlogm + nlogn) time
[1 3 5 7]
[2 4 6 8]

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

    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                v.emplace_back(i, nums[i]);
            }
        }
    }

    int getIdx(int i) {
        return v[i].first;
    }

    int getNum(int i) {
        return v[i].second;
    }

    int getDim() {
        return v.size();
    }

    int lower_bound(int b, int e, int idx) {
        // return std::lower_bound(begin(v) + b, begin(v) + e, idx, [](const auto &p, int idx){ return p.first < idx; }) - begin(v); // 这个lambda相当于实现一个less，即找到第一个不小于的为止
        return std::lower_bound(begin(v) + b, begin(v) + e, make_pair(idx, INT_MIN)) - begin(v);
    }

    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int res = 0;
        for (int i = 0, j = 0, m = getDim(), n = vec.getDim(); i < m && j < n;) {
            int ii = getIdx(i), ij = vec.getIdx(j);
            if (ii == ij) {
                res += getNum(i++) * vec.getNum(j++);
            } else if (ii < ij) {
                i = lower_bound(i + 1, m, ij);
            } else {
                j = vec.lower_bound(j + 1, n, ii);
            }
        }
        return res;
    }

    vector<pair<int, int>> v;
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

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

build graph O(mn) time
topological sort O(v+e) time
这里[“ab”, “abc”]以及[“z”, “z”]都是合法的，返回任一结果即可，但是[“abc”, “ab”]是非法的，必须返回空串

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
class Solution {
public:
    string alienOrder(vector<string>& words) {
        string u;
        for (auto v : words) { // 这个必须是deep copy因为后边要修改
            for (auto c : v) {
                if (!g.count(c)) {
                    g[c] = {}; // 需要对unordered_set初始化否则结果不完整会丢字符
                }
            }
            int n = min(u.length(), v.length()), i = 0;
            for (; i < n; ++i) { // 比较前后两个字符串的每个字符，如果发现不一样的加一条边
                if (u[i] != v[i]) {
                    g[u[i]].insert(v[i]);
                    break;
                }
            }
            if (i == n && u.length() > v.length()) return ""; // ["abc", "ab"]非法
            u.swap(v);
        }
        visited.resize(128);
        for (auto [c, _] : g) {
            if (!isAcyclic(c)) return "";
        }
        return string(rbegin(s), rend(s));
    }

    bool isAcyclic(char u) {
        if (visited[u]) return visited[u] == 1;
        visited[u] = -1;
        for (auto v : g[u]) {
            if (!isAcyclic(v)) return false;
        }
        s += u;
        visited[u] = 1;
        return true;
    }

    string s;
    unordered_map<char, unordered_set<char>> g; // 用unordered_set去重
    vector<char> visited; // -1 0 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
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size() == 1) return words[0];
        auto cmp = [](const string &a, const string &b) {return a.length() < b.length();};
        int n = words.size(), m = max_element(begin(words), end(words), cmp)->length();
        vector<bool> isOrdered(n - 1);
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n - 1; ++i) {
                if (!isOrdered[i]) {
                    if (words[i].length() <= j) {
                        isOrdered[i] = true;
                    } else if (words[i][j] != words[i + 1][j]) {
                        isOrdered[i] = true;
                        g[words[i][j]].insert(words[i + 1][j]);
                        if (g.count(words[i + 1][j]) == 0) {
                            g[words[i + 1][j]] = {};
                        }
                    }
                }
                if (j < words[i].length() && g.count(words[i][j]) == 0) {
                    g[words[i][j]] = {};
                }
                if (j < words[i + 1].length() && g.count(words[i + 1][j]) == 0) {
                    g[words[i + 1][j]] = {};
                }
            }
        }
        visited.resize(128);
        for (auto &&p : g) {
            if (!ts(p.first)) return "";
        }
        string res;
        while (!s.empty()) {
            res += s.top();
            s.pop();
        }
        return res;
    }

    bool ts(char ch) {
        if (visited[ch] == 1) return true;
        if (visited[ch] == -1) return false;
        visited[ch] = -1;
        for (auto &&c : g[ch]) {
            if (!ts(c)) return false;
        }
        s.push(ch);
        visited[ch] = 1;
        return true;
    }

    vector<int> visited;
    stack<char> s;
    unordered_map<char, unordered_set<char>> g;
};

followup: All results of Alien Dictionary

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
class Solution {
public:
    vector<string> alienOrder(vector<string> words) {
        string u;
        for (auto v : words) {
            for (char c : v) {
                if (g.count(c) == 0) {
                    g[c] = {};
                }
            }
            int len = min(u.length(), v.length()), i = 0;
            for (; i < len; ++i) { // 比较前后两个字符串的每个字符，如果发现不一样的加一条边
                if (u[i] != v[i]) {
                    g[u[i]].insert(v[i]);
                    break;
                }
            }
            if (i == len && u.length() > v.length()) return {}; // ["abc", "ab"]非法
            u.swap(v);
        }
        n = g.size();
        visited.resize(128);
        dfs(0);
        return res;
    }

    void dfs(int b) {
        if (b == n) {
            res.push_back(s);
            return;
        }
        for (auto [c, _] : g) {
            if (visited[c] || !isValid(c)) continue;
            visited[c] = true;
            s += c;
            dfs(b + 1);
            s.pop_back();
            visited[c] = false;
        }
    }

    bool isValid(char c) {
        for (char t : s) {
            if (g[c].count(t)) return false;
        }
        return true;
    }

    int n;
    vector<bool> visited;
    string s;
    vector<string> res;
    unordered_map<char, unordered_set<char>> g;
};

int main() {
    Solution sol;
    for (auto s : sol.alienOrder({"wrt","wrf","er","ett","rftt"})) {
        cout<<s<<endl;
    }
    return 0;
}