2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集
题目描述
给定两个字符串s1和s2和正整数K，其中s1长度为n1，s2长度为n2，在s2中选一个子串，满足:
- 该子串长度为n1+k
- 该子串中包含s1中全部字母，
- 该子串每个字母出现次数不小于s1中对应的字母，
我们称s2以长度k冗余覆盖s1，给定s1，s2，k，求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标，如果没有返回**-1**。
输入描述
输入三行，第一行为s1；
第二行为s2；
第三行为k；
s1和s2只包含小写字母
输出描述
最左侧的s2以长度k冗余覆盖s1的子串首个元素下标，如果没有返回**-1。**
示例1
输入：
ab
aabcd
1输出：
0说明：
子串aab和abc符合要求，由于aab在abc的左侧，因此输出aab的下标：0
示例2
输入：
abc
dfs
10输出：
-1说明：
s2无法覆盖s1，输出 -1
C++
#include <bits/stdc++.h>using namespace std;int main() {string s1, s2;int k;cin >> s1;cin >> s2;cin >> k;int n1 = s1.size(), n2 = s2.size();// 记录 s1 中每个字符出现的次数int cnt1[26] = {0};for (char c: s1) cnt1[c - 'a']++;// 用于记录s2滑动窗口上的子字符串中的每个字符出现的次数int cnt2[26] = {0};int l = 0, r = 0;while (r < n2) {cnt2[s2[r++] - 'a']++;// 子串长度不足 n1 + k 时继续扩大窗口if (r < n1 + k) continue;// 使保持窗口大小为 n1 + kif (r - l > n1 + k) cnt2[s2[l++]]--;// 判断当前子字符串 s[l:r] 是否冗余覆盖 s1 中所有字母bool cover = true;for (int i = 0; i < 26; i++) {if (cnt1[i] > cnt2[i]) {cover = false;break;}}// 找到冗余覆盖的子字符串if (cover) {cout << l << endl;return 0;}}// 没有找到符合要求的子字符串cout << -1 << endl;return 0;
}
题目分析
这个问题要求我们找到一个子串，使得该子串长度为
n1 + k，并且能够冗余覆盖s1中的所有字母，即该子串中每个字母的出现次数至少是s1中相应字母的出现次数。要求我们找到最左边的符合条件的子串，并输出其起始位置。解题思路
这个问题本质上是一个滑动窗口问题，我们可以通过维护一个窗口来扫描字符串
s2。具体步骤如下：
字符频率统计：
- 先统计字符串
s1中每个字符的出现次数，记录在数组cnt1中。- 然后在
s2中维护一个滑动窗口，该窗口的大小是n1 + k，并记录该窗口中每个字符的出现次数，保存在cnt2数组中。滑动窗口：
- 从
s2的第一个字符开始，窗口的右边界逐渐向右扩展，直到窗口的大小为n1 + k。- 每次扩展窗口时，更新
cnt2数组，记录当前窗口中每个字符的出现次数。- 如果窗口的大小超过了
n1 + k，则左边界向右移动，保持窗口大小不变，并更新cnt2数组。判断冗余覆盖：
- 每次更新窗口时，我们检查当前窗口中的字符频率是否能够满足冗余覆盖
s1的条件。具体来说，检查cnt2中每个字符的数量是否都大于等于cnt1中相应字符的数量。结果输出：
- 如果找到了符合条件的子串，输出其左边界索引。
- 如果扫描完整个
s2后没有找到符合条件的子串，输出-1。时间复杂度分析
- 滑动窗口的右边界
r会遍历整个s2字符串，因此时间复杂度是 O(n2)，其中n2是s2的长度。- 对每个滑动窗口，检查是否满足冗余覆盖需要遍历 26 个字母，因此检查过程的时间复杂度是 O(26) ≈ O(1)。
- 总的时间复杂度是 O(n2)。
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏