【最新华为OD机试E卷】最左侧冗余覆盖子串(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🎀 最左侧冗余覆盖子串

问题描述

给定两个字符串 和 和正整数 ，其中 长度为 ， 长度为 ，在 中选一个子串，满足：

• 该子串长度为
• 该子串中包含 中全部字母
• 该子串每个字母出现次数不小于 中对应的字母

我们称 以长度 冗余覆盖 ，给定 ，，，求最左侧的 以长度 冗余覆盖 的子串的首个元素的下标，如果没有返回 -1。

输入格式

输入三行：

• 第一行为字符串
• 第二行为字符串
• 第三行为整数

和 只包含小写字母。

输出格式

输出一个整数，表示最左侧的 以长度 冗余覆盖 的子串首个元素下标，如果没有返回 -1。

样例输入

ab
aabcd
1

样例输出

0

样例解释

无

数据范围

题解

这道题目本质上是一个滑动窗口问题，。解题思路如下：

1. 首先，统计 中每个字符的出现次数。
2. 使用滑动窗口在 上移动，窗口大小为 。
3. 对于每个窗口，统计窗口内字符的出现次数。
4. 比较窗口内的字符统计与 的字符统计，检查是否满足冗余覆盖的条件。
5. 如果满足条件，返回窗口的起始索引；如果遍历完所有窗口都不满足，返回 -1。

关键点解释：

• 使用数组或哈希表来存储字符计数，可以快速进行比较。
• 滑动窗口技巧可以避免重复计算，提高效率。

时间复杂度分析：

• 统计 的字符次数：
• 滑动窗口遍历 ：
• 每次窗口移动时的字符计数比较：（因为只有小写字母）

总体时间复杂度：

参考代码

• Python

def check_redundancy(s1_count, window_count):
    """
    检查窗口是否冗余覆盖s1
    """
    return all(window_count.get(c, 0) >= s1_count[c] for c in s1_count)

def find_redundant_substring(s1, s2, k):
    """
    寻找s2中冗余覆盖s1的子串
    """
    n1, n2 = len(s1), len(s2)
    window_size = n1 + k
    
    if window_size > n2:
        return -1
    
    # 统计s1中字符出现次数
    s1_count = {}
    for c in s1:
        s1_count[c] = s1_count.get(c, 0) + 1
    
    # 初始化窗口
    window_count = {}
    for c in s2[:window_size]:
        window_count[c] = window_count.get(c, 0) + 1
    
    # 检查第一个窗口
    if check_redundancy(s1_count, window_count):
        return 0
    
    # 滑动窗口
    for i in range(1, n2 - window_size + 1):
        # 移除窗口左边的字符
        window_count[s2[i-1]] -= 1
        if window_count[s2[i-1]] == 0:
            del window_count[s2[i-1]]
        
        # 添加窗口右边的新字符
        window_count[s2[i+window_size-1]] = window_count.get(s2[i+window_size-1], 0) + 1
        
        # 检查当前窗口
        if check_redundancy(s1_count, window_count):
            return i
    
    return -1

# 读取输入
s1 = input().strip()
s2 = input().strip()
k = int(input())

# 计算并输出结果
result = find_redundant_substring(s1, s2, k)
print(result)

• C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_LEN 100001

bool check_redundancy(int s1_count[], int window_count[]) {
    for (int i = 0; i < 26; i++) {
        if (window_count[i] < s1_count[i]) {
            return false;
        }
    }
    return true;
}

int find_redundant_substring(char s1[], char s2[], int k) {
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    int window_size = n1 + k;
    
    if (window_size > n2) {
        return -1;
    }
    
    int s1_count[26] = {0};
    int window_count[26] = {0};
    
    // 统计s1中字符出现次数
    for (int i = 0; i < n1; i++) {
        s1_count[s1[i] - 'a']++;
    }
    
    // 初始化窗口
    for (int i = 0; i < window_size; i++) {
        window_count[s2[i] - 'a']++;
    }
    
    // 检查第一个窗口
    if (check_redundancy(s1_count, window_count)) {
        return 0;
    }
    
    // 滑动窗口
    for (int i = 1; i <= n2 - window_size; i++) {
        window_count[s2[i-1] - 'a']--;
        window_count[s2[i+window_size-1] - 'a']++;
        
        if (check_redundancy(s1_count, window_count)) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char s1[MAX_LEN], s2[MAX_LEN];
    int k;
    
    scanf("%s", s1);
    scanf("%s", s2);
    scanf