leetcode biweekly contes 107

第三题是个好题目，第四题确实是常规题目。

6892. 最大字符串配对数目

给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。

如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：

字符串 words[i] 等于 words[j] 的反转字符串。
0 <= i < j < words.length

请你返回数组 words 中的最大匹配数目。

注意，每个字符串最多匹配一次。

示例 1：

输入：words = ["cd","ac","dc","ca","zz"]
输出：2
解释：在此示例中，我们可以通过以下方式匹配 2 对字符串：
- 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 "dc" 并且等于 words[2]。
- 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 "ca" 并且等于 words[3]。
可以证明最多匹配数目是 2 。

示例 2：

输入：words = ["ab","ba","cc"]
输出：1
解释：在此示例中，我们可以通过以下方式匹配 1 对字符串：
- 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 "ab" 与 words[0] 相等。
可以证明最多匹配数目是 1 。

示例 3：

输入：words = ["aa","ab"]
输出：0
解释：这个例子中，无法匹配任何字符串。

提示：

1 <= words.length <= 50
words[i].length == 2
words 包含的字符串互不相同。
words[i] 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-107/problems/find-maximum-number-of-string-pairs/

题意

直接模拟

思路

对每个元素进行标记，如果已经访问过的则不再访问，否则依次查找可以配对的元素即可。
复杂度分析：

时间复杂度：$O(nm)$，其中 $n$ 表示数组的长度， $m$ 表示字符串的平均长度。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        int n = words.size();
        vector<bool> visit(n, false);
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                for (int j = i + 1; j < n; j++) {
                    if (!visit[j]) {
                        string t = words[j];
                        reverse(t.begin(), t.end());
                        if (words[i] == t) {
                            res++;
                            visit[i] = true;
                            visit[j] = true;
                        }
                    }
                }
            }
        }
        return res;
    }
};

6895. 构造最长的新字符串

给你三个整数 x ，y 和 z 。

这三个整数表示你有 x 个 "AA" 字符串，y 个 "BB" 字符串，和 z 个 "AB" 字符串。你需要选择这些字符串中的部分字符串（可以全部选择也可以一个都不选择），将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 "AAA" 或者 "BBB" 。

请你返回新字符串的最大可能长度。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：x = 2, y = 5, z = 1
输出：12
解释： 我们可以按顺序连接 "BB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AB" ，得到新字符串 "BBAABBAABBAB" 。
字符串长度为 12 ，无法得到一个更长的符合题目要求的字符串。

示例 2：

输入：x = 3, y = 2, z = 2
输出：14
解释：我们可以按顺序连接 "AB" ，"AB" ，"AA" ，"BB" ，"AA" ，"BB" 和 "AA" ，得到新字符串 "ABABAABBAABBAA" 。
字符串长度为 14 ，无法得到一个更长的符合题目要求的字符串。

提示：

1 <= x, y, z <= 50

地址

https://leetcode.cn/contest/biweekly-contest-107/problems/construct-the-longest-new-string/

题意

数学逻辑

思路

我们可以观察到 $AA$ 或者 $BB$ 任意两个相同的元素之间必须要要插入其他的元素， $AB$ 无法重复多少次即可。
- 假设 $AA$ 的数量与 $BB$ 的数量相等，此时我们可以按照$AABBAABB\cdots BBAB\cdots$ 来排序即可；
- 假设 $AA$ 的数量与 $BB$ 的数量不相等，此时我们分析一下，无论如何连续的 $AA$ 或者 $BB$ 之间只能插入 $BB$ 或者 $AA$ 而不能插入 $AB$, 因此 $BB$ 必须与 $AA$ 间隔放置，到底可以放置多少个 $BB$ 与 $AA$，假设 $AA$ 的数量为 $x$, $BB$ 的数量为 $y$:
  - 假设 $AA$ 的数量少于 $BB$ 的数量，$AB$ 可以放置到右侧，接下来连续放置 $BB$ 与 $AA$ ，则此时可以知道最多可以连续放置 $x$ 个 $AA$ 与 $x+ 1$ 个 $BB$, 然后紧接着放置 $z$ 个 $AB$, 顺序为: $BBAABB\cdots BBAB\cdots$ 来排序即可；
  - 假设 $AA$ 的数量多于 $BB$ 的数量，$AB$ 可以放置到左侧，接下来连续放置 $AA$ 与 $BB$ ，左侧先放置 $z$ 个 $AB$, 最多可以连续放置 $y$ 个 $BB$ 与 $y+ 1$ 个 $AA$, 顺序为: $AB\cdots ABAABB\cdots AA$ 来排序即可；
复杂度分析：

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int longestString(int x, int y, int z) {
        if (x == y) {
            return 2* (x + y + z);
        } else {
            return (2 * min(x, y) + 1 + z) * 2;
        }
    }
};

6898. 字符串连接删减字母

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。

定义连接操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被删除。

比方说 join("ab", "ba") = "aba" ， join("ab", "cde") = "abcde" 。

你需要执行 n - 1 次连接操作。令 str0 = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：

令 stri = join(stri - 1, words[i])
令 stri = join(words[i], stri - 1)

你的任务是使 strn - 1 的长度最小。

请你返回一个整数，表示 strn - 1 的最小长度。

示例 1：

输入：words = ["aa","ab","bc"]
输出：4
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc" 
str2 的最小长度为 4 。

示例 2：

输入：words = ["ab","b"]
输出：2
解释：这个例子中，str0 = "ab"，可以得到两个不同的 str1：
join(str0, "b") = "ab" 或者 join("b", str0) = "bab" 。
第一个字符串 "ab" 的长度最短，所以答案为 2 。

示例 3：

输入：words = ["aaa","c","aba"]
输出：6
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = "aaa"
str1 = join(str0, "c") = "aaac"
str2 = join("aba", str1) = "abaaac"
str2 的最小长度为 6 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 50
words[i] 中只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-107/problems/decremental-string-concatenation/

题意

动态规划

思路

动态规划，设 $dp[i][j][k]$ 表示前 $i$ 个字符串合并后中以 $j$ 为开头，以 $k$ 为结尾的字符串的最小长度，此时可以知道递推公式如下:
$$
dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][l][k] + l_{i + 1} \quad if r \neq k \
dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][l][k] + l_{i + 1} - 1 \quad if r = k \
dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][r] + l_{i + 1} \quad if k \neq l \
dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][r] + l_{i + 1} - 1 \quad if k = l \
$$
- 当我们添加一个字符串时 $s[i+1]$ 时，如果 $s[i+1]$ 的前后字符串没有与之前的前后字符串相等，则此时的最小长度即等于之前的最小长度加上 $l_{i+1}$, 此时 $s[i+1]$ 可以加在当前字符的最前面或者最后面；
- 当我们添加一个字符串时 $s[i+1]$ 时，如果 $s[i+1]$ 的第一个字符与合并后的字符串的最后一个字符相等，则此时可以进行合并，将 $s[i+1]$ 插入到字符串后面，，则此时的最小长度即等于之前的最小长度加上 $l_{i+1} - 1$；
- 当我们添加一个字符串时 $s[i+1]$ 时，如果 $s[i+1]$ 的最后一个字符与合并后的字符串的第一个字符相等，则此时可以进行合并，将 $s[i+1]$ 插入到字符串前面，，则此时的最小长度即等于之前的最小长度加上 $l_{i+1} - 1$；
复杂度分析：

时间复杂度：$O(n\times |\Sigma|^2)$，其中 $n$ 为给定的数组的长度， $|\Sigma|$ 表示字符集的大小；
空间复杂度：$O(|\Sigma|^2)$，其中 $|\Sigma|$ 表示字符集的大小；

代码

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> dp(26, vector<int>(26, INT_MAX));
        dp[words[0].front() - 'a'][words[0].back() - 'a'] = words[0].size();
        for (int i = 1; i < n; i++) {
            int l = words[i].front() - 'a';
            int r = words[i].back() - 'a';
            int m = words[i].size();
            vector<vector<int>> ndp(26, vector<int>(26, INT_MAX));
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    if (dp[j][k] == INT_MAX) continue;
                    ndp[l][k] = min(ndp[l][k], dp[j][k] + m - (r == j ? 1 : 0)); 
                    ndp[j][r] = min(ndp[j][r], dp[j][k] + m - (l == k ? 1 : 0));
                }
            }
            dp = move(ndp);
        }
        int res = INT_MAX;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                res = min(res, dp[i][j]);
            }
        }
        return res;
    }
};

6468. 统计没有收到请求的服务器数目

给你一个整数 n ，表示服务器的总数目，再给你一个下标从 0 开始的二维整数数组 logs ，其中 logs[i] = [server_id, time] 表示 id 为 server_id 的服务器在 time 时收到了一个请求。

同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries 。

请你返回一个长度等于 queries.length 的数组 arr ，其中 arr[i] 表示在时间区间 [queries[i] - x, queries[i]] 内没有收到请求的服务器数目。

注意时间区间是个闭区间。

示例 1：

输入：n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
输出：[1,2]
解释：
对于 queries[0]：id 为 1 和 2 的服务器在区间 [5, 10] 内收到了请求，所以只有服务器 3 没有收到请求。
对于 queries[1]：id 为 2 的服务器在区间 [6,11] 内收到了请求，所以 id 为 1 和 3 的服务器在这个时间段内没有收到请求。

示例 2：

输入：n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
输出：[0,1]
解释：
对于 queries[0]：区间 [1, 3] 内所有服务器都收到了请求。
对于 queries[1]：只有 id 为 3 的服务器在区间 [2,4] 内没有收到请求。

提示：

1 <= n <= 105
1 <= logs.length <= 105
1 <= queries.length <= 105
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 106
1 <= x <= 105
x < queries[i] <= 106

地址

https://leetcode.cn/contest/biweekly-contest-107/problems/count-zero-request-servers/

题意

滑动窗口

思路

典型的滑动窗口，我们首先将所的服务器请求按照时间先后顺序排序，然后将查询也按照时间先后顺序排序。

每次我们固定查询的时间窗口为 $[start, end]$, 此时统计当前在该区域中服务器的数量，此时我们可以利用哈希表统计即可，用 $[l,r]$ 表示当前窗口，此时我们首先将 $r$ 移动到 $end$ 处，对于服务器的统计数目依次加 $1$, 然后移动左侧 $l$ 移动至 $start$ 处，将不在窗口窗口区域的数据全部删除掉即可，比较简单的滑动窗口实现即可，比较关键的一点需要先移动右边届，再移动左边界。
利用上述变换即可。
复杂度分析：

时间复杂度：$O(n + m)$，其中 $n$ 表示给定 $logs$ 数组长度， $m$ 表示 $queries$ 数组的长度。
空间复杂度：$O(n + m)$，其中 $n$ 表示给定 $logs$ 数组长度， $m$ 表示 $queries$ 数组的长度。

代码

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        int m = logs.size();
        sort(logs.begin(), logs.end(), [&](const vector<int> & a, const vector<int> &b) {
            return a[1] < b[1];
        });
        vector<pair<int, int>> arr;
        for (int i = 0; i < queries.size(); i++) {
            arr.emplace_back(queries[i], i);
        }
        sort(arr.begin(), arr.end());
        vector<int> res(queries.size());
        unordered_map<int, int> cnt;
        int l = 0, r = 0;
        int pre = 0;
        for (int i = 0; i < arr.size(); i++) {
            auto [end, idx] = arr[i];
            int start = end - x;
            while (r < m && logs[r][1] <= end) {
                cnt[logs[r][0]]++;
                r++;
            }
            while (l < m && logs[l][1] < start) {
                cnt[logs[l][0]]--;
                if (cnt[logs[l][0]] == 0) {
                    cnt.erase(logs[l][0]);
                }
                l++;
            }            
            res[idx] = n - cnt.size();
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 351 leetcode weekly contes 352 →

扫描二维码，分享此文章