LeetCode weekly contest 245

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
1904 / 12724 YoungForest 12 1:39:20 0:02:52 1:24:20 🐞 3 0:21:30 null

零神大数据：
1897,Redistribute Characters to Make All Strings Equal,redistribute-characters-to-make-all-strings-equal,1309.1422268153
1898,Maximum Number of Removable Characters,maximum-number-of-removable-characters,1912.8440554296
1899,Merge Triplets to Form Target Triplet,merge-triplets-to-form-target-triplet,1635.6879273926
1900,The Earliest and Latest Rounds Where Players Compete,the-earliest-and-latest-rounds-where-players-compete,2454.7653333657

今天的周赛翻车了。第二题一开始算错时间复杂度了，一直妄图找到更优算法。之后看到80人提交才重新审视二分暴力的时间复杂度，竟然是没问题的。实现过程中又遇到1次WA（判断子序列时，相等字符忘记更新s的下标了），2次TLE（标记remove下标不能用unordered_set, 而要用vector。算是被卡常数了)。这周又要残酷打卡了，幸运的是，因为前2周的成绩比较好，本周残酷榜更新后我的排名不降反升。

1897. Redistribute Characters to Make All Strings Equal

签到题。本质是判断所有的字符是否可以平均分配到n个单词中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool makeEqual(vector<string>& words) {
        const int n = words.size();
        vector<int> cnt(26, 0);
        for (const auto& word : words) {
            for (char c : word) {
                ++cnt[c - 'a'];
            }
        }
        for (int i : cnt) {
            if (i % n != 0) return false;
        }
        return true;
    }
};

时间复杂度: O(sum(words[i].length)),
空间复杂度: O(1).

1898. Maximum Number of Removable Characters

最优化问题转判定问题（双指针判断是否是子序列），二分搜索。

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
class Solution {
    using ll = int;
    vector<bool> mark = vector<bool>(1e5);
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        const int n = removable.size();
        auto binary = [&](ll lo, ll hi, function<bool(const ll)> predicate) -> int {
            while (lo < hi) {
                ll mid = lo + (hi - lo) / 2;
                if (!predicate(mid)) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return lo;
        };
        // cout << s.size() << endl;
        // cout << n << endl;
        return binary(0, n + 1, [&](const ll x) -> bool {
            for (int i = 0; i < s.size(); ++i) {
                mark[i] = false;
            }
            for (int i = 0; i < x; ++i) {
                mark[removable[i]] = true;
            }
            int pi = 0, si = 0;
            while (pi < p.size()) {
                while (si < s.size() && (mark[si] || s[si] != p[pi])) ++si;
                if (si == s.size()) 
                {
                    // cout << x << ":false"  << endl;
                    return false;
                }
                // if (s[si] != p[pi]) cout << "impossible" << endl;
                ++si;
                ++pi;
            }
            // cout << x << ":true "<< si   << endl;
            return true;
        }) - 1;
    }
};

时间复杂度: O(log removable.length * (s.length + p.length)),
空间复杂度: O(s.length).

本题有个坑是说，标记s中哪些位置被标记时，不能用unordered_set（即使加reserve)，会超时。可以用vector<bool>。算是被卡常数了。

1899. Merge Triplets to Form Target Triplet

因为每次合并操作是去最大值，因此，只要有一个数大于target的triplet不能用。
所以把剩下可以用的都合并了，看能不能达到target。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        vector<int> cnt(3, 0);
        for (int i = 0; i < 3; ++i) {
            for (const auto& v : triplets) {
                if (v[i] == target[i] && v[(i + 1) % 3] <= target[(i + 1) % 3] && v[(i + 2) % 3] <= target[(i + 2) % 3]) {
                    ++cnt[i];
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            if (cnt[i] == 0) return false;
        }
        return true;
    }
};

时间复杂度: O(triplets.length),
空间复杂度: O(1).

1900. The Earliest and Latest Rounds Where Players Compete

TNL~