华为OD机试真题 Java 实现【最左侧冗余覆盖子串】【2023Q2 100分】，附详细解题思路

目录

• • 专栏导读
  • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • 四、解题思路
  • 五、Java算法源码
  • 六、效果展示

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。

• 专栏福利：限时订阅49.9，订阅后可加入华为OD刷题群，获得哪吒优先答疑机会（华为OD刷题指导，远程代码调试），群里大佬众多可以抱团取暖，群友刷题经验分享，考试经验分享。

一、题目描述

给定两个字符串 s1 和 s2 和正整数k，其中 s1 长度为 n1，s2 长度为 n2， 在s2中选一个子串，满足:

1. 该子串长度为n1+k；
2. 该子串中包含s1中全部字母；
3. 该子串每个字母出现次数不小于s1中对应的字母， 我们称s2以长度k冗余覆盖s1， 给定s1，s2，k, 求最左侧的s2以长度k冗余覆盖s1的
   子串的首个元素的下标， 如果没有返回-1。

二、输入描述

输入为三行：

1. 第一行为 s1
2. 第二行为 s1
3. 第三行为 k

s1和s2都只包含小写字母。

三、输出描述

最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素下标，若不存在，则返回-1。

四、解题思路

1. 读取输入的字符串s1、s2和正整数k；
2. 如果s2的长度小于s1的长度加上k，直接输出-1；
3. 初始化一个大小为128的整型数组arr，用于记录s1中每个字母出现的次数；
4. 遍历字符串s1，将每个字母出现的次数记录在arr数组中；
5. 初始化变量num为s1的长度，表示需要匹配的字母个数；
6. 在长度为n1+k的子串中，遍历每个字符：
   • 如果该字符在arr数组中的计数大于0，则将arr数组对应位置的计数减1，并将num减1；
   • 如果num变为0，表示已经找到满足条件的子串，输出首个元素下标0并返回；
7. 对于长度大于n1+k的子串，从下标1开始遍历到s2的长度减去n1-k：
   • 如果arr数组中下标为i-1的计数大于等于0，则将num加1；
   • 如果arr数组中下标为i-1+s1的长度+k的计数大于0，则将arr数组对应位置的计数减1，并将num减1；
   • 如果num变为0，表示已经找到满足条件的子串，输出首个元素下标i并返回；
8. 如果没有找到满足条件的子串，则输出-1；

五、Java算法源码

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s1 = in.nextLine();
    String s2 = in.nextLine();
    int k = in.nextInt();

    if (s2.length() < s1.length() + k) {
        System.out.println(-1);
        return;
    }

    int[] arr = new int[128];
    for (int i = 0; i < s1.length(); i++) {
        arr[s1.charAt(i)] += 1;
    }

    int num = s1.length();

    for (int j = 0; j < s1.length() + k; j++) {
        if (arr[s2.charAt(j)]-- > 0) {
            num--;
        }

        if (num == 0) {
            System.out.println(0);
            return;
        }
    }

    for (int i = 1; i <= s2.length() - s1.length() - k; i++) {
        if (arr[s2.charAt(i - 1)]++ >= 0) {
            num++;
        }

        if (arr[s2.charAt(i - 1 + s1.length() + k)]-- > 0) {
            num--;
        }

        if (num == 0) {
            System.out.println(i);
            return;
        }
    }

    System.out.println(-1);
}

六、效果展示

1、输入

ab
aabcd
1

2、输出

0

3、思路

🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。