Skip to content

第 325 场周赛

比赛链接

Date: 2022-12-25

A 到目标字符串的最短距离

暴力即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int closetTarget(vector<string>& words, string target, int startIndex) {
        int n = words.size();
        int res = n;
        for (int i = 0; i < n; i++) {
            if (words[(startIndex + i) % n] == target) {
                res = i;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (words[(startIndex - i + n) % n] == target) {
                res = min(res, i);
            }
        }
        if (res == n) return -1;
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(nm)\)
  • 空间复杂度：\(O(1)\)

B 每种字符至少取 K 个

双指针，哈希，贪心

 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 takeCharacters(string s, int k) {
        int n = s.size();
        vector<int> a(n + 1), b(n + 1), c(n + 1);
        int A = 0, B = 0, C = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'a') A++;
            else if (s[i] == 'b') B++;
            else C++;
            a[i + 1] = A;
            b[i + 1] = B;
            c[i + 1] = C;
        }
        if (A < k || B < k || C < k) return -1;
        int i = s.size();
        while (i > 0 && a[i - 1] >= k && b[i - 1] >= k && c[i - 1] >= k) i--;

        int res = i;
        A = 0, B = 0, C = 0;
        for (int j = s.size() - 1; j >= 0; j--) {
            if (s[j] == 'a') A++;
            else if (s[j] == 'b') B++;
            else C++;
            while (i > 0 && (a[i - 1] + A) >= k && (b[i - 1] + B) >= k && (c[i - 1] + C) >= k) i--;
            res = min(res, i + (int) s.size() - j);
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

C 礼盒的最大甜蜜度

二分

 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:
    int maximumTastiness(vector<int>& p, int k) {
        sort(p.begin(), p.end());
        int l = 0, r = 1E9;
        auto check = [&](int x) {
            int last = p[0], cnt = 1;
            for (int i = 1; i < p.size(); i++) {
                if (p[i] - last >= x) {
                    last = p[i];
                    cnt++;
                }
            }
            return cnt >= k;
        };
        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (check(m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
};

复杂度分析

  • 时间复杂度：\(O(n\log C)\)
  • 空间复杂度：\(O(1)\)

D 好分区的数目

先求出所有区分的数目 \(2^n\)，然后求出不是好区分的数目（从中选出小于 \(k\) 的方案数），两者减去就是答案。

class Solution {
public:
    static constexpr int mod = 1E9 + 7;
    int countPartitions(vector<int>& nums, int k) {
        long long s = accumulate(nums.begin(), nums.end(), 0ll);
        if (s < 2 * k) return 0;
        int sum = 1;
        for (int i = 0; i < nums.size(); i++) sum = sum * 2 % mod;
        vector<int> d(k + 1);
        d[0] = 1;
        for (auto x : nums) {
            for (int i = k; i >= x; i--) {
                d[i] = (d[i] + d[i - x]) % mod;
            }
        }
        int res = 0;
        for (int i = 0; i < k; i++) {
            res = (res + d[i]) % mod;
        }
        res = res * 2 % mod;
        return ((sum - res) % mod + mod) % mod;
    }
};

复杂度分析

  • 时间复杂度：\(O(nk)\)
  • 空间复杂度：\(O(k)\)

T2 细节比较多，被卡了很久

本文访问 次