LOADING

百度&必应权4, 日IP8000. 查看详情
自助收录

2023年华为OD机考真题:最左侧冗余覆盖子串

算法刷题1年前 (2023)更新 江南白衣
455 0 0
2023年华为OD机考真题:最左侧冗余覆盖子串

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:最左侧冗余覆盖子串
知识点:滑动窗口
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
给定2个字符串s1和s2和正整数k,其中s1长度为n1,s2长度为n2,在s2中选一个子串,满足:
该子串长度为n1+k
该子串包含s1中全部字母
该子串每个字母的出现次数不小于s1中对应的字母
我们称s2以长度k冗余覆盖s1。给定s1、s2和k,求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标,如果没有返回-1
举例:
s1=ab
s2=aabcd
k=1
则子串aab和abc均满足此条件,由于aab在abc的左侧,aab的第一个元素下标为0,因此输出0
输入描述:
输入三行,第一行为s1,第二行为s2,第三行为k
s1和s2只包含小写字母
输出描述:
最左侧的s2以长度k冗余覆盖s1的子串首个元素的下标,如果没有返回-1
补充说明:
0 <= len(s1) <= 1000000
0 <= len(s2) <= 20000000
0 <= k <= 1000
示例1
输入:
ab
aabcd
1
输出:
0
说明:
子串aab和abc满足要求,由于aab在abc的左侧,因此输出aab的下下标:0
示例2
输入:
abc
dfs
10
输出:
-1
说明:
s2无法覆盖s1,输出-1
解题思路:
通过s1的长度和k值计算出父字符串的长度
从s2遍历中截取步骤1的长度的字符串作为父字符串
通过双层for循环,求出s1是否为步骤2中的子串
代码实现一:

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最左侧冗余覆盖子串
 * @Description 给定2个字符串s1和s2和正整数k,其中s1长度为n1,s2长度为n2,在s2中选一个子串,满足:
 * 该子串长度为n1+k
 * 该子串包含s1中全部字母
 * 该子串每个字母的出现次数不小于s1中对应的字母
 * 我们称s2以长度k冗余覆盖s1。给定s1、s2和k,求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标,如果没有返回-1
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n1 = sc.nextLine();
        String n2 = sc.nextLine();
        int k = sc.nextInt();
        int res = -1;
        int strLen = n1.length() + k;
        for (int i = 0; i < n2.length() - strLen + 1; i++) {
            char[] chars = n2.substring(i, i + strLen).toCharArray();
            if (qiuzichuan(n1, chars)) {
                res = i;
                break;
            }
        }
        System.out.println(res);
    }

    public static boolean qiuzichuan(String s1, char[] chars) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < chars.length; j++) {
                if (s1.charAt(i) == chars[j]) {
                    chars[j] = ' ';
                    count++;
                    break;
                }
            }
        }
        return count == s1.length();
    }

}

代码实现二:

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最左侧冗余覆盖子串
 * @Description 给定2个字符串s1和s2和正整数k,其中s1长度为n1,s2长度为n2,在s2中选一个子串,满足:
 * 该子串长度为n1+k
 * 该子串包含s1中全部字母
 * 该子串每个字母的出现次数不小于s1中对应的字母
 * 我们称s2以长度k冗余覆盖s1。给定s1、s2和k,求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标,如果没有返回-1
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int n1 = s1.length(); // 0 <= n1 <= 1000000
        int n2 = s2.length(); // 0 <= n2 <= 20000000
        int k = in.nextInt(); // 冗余 0 <= k <= 1000
        int subLen = n1 + k; // 子串长度
        // s2长度不满足冗余长度
        if (n2 < subLen) {
            System.out.print("-1");
            return;
        }
        // 记录子串中26个字母出现的次数
        int[] charCountArr = new int[26];
        // 用最左子串初始化
        String sub0 = s2.substring(0, 0 + subLen);
        for (char c : sub0.toCharArray()) {
            charCountArr[c - 'a']++;
        }
        int[] charArrS1 = new int[26];
        for (char c : s1.toCharArray()) {
            charArrS1[c - 'a']++;
        }
        // 从最左侧遍历,遇到一个满足条件的子串即可
        int firstChar = s2.charAt(0);
        for (int i = 0; i <= n2 - subLen; i++) {
            char newChar = s2.charAt(i + subLen - 1);
            if (i > 0) {
                // 每次取新的子串,就将字符数组更新
                charCountArr[firstChar - 'a']--;
                charCountArr[newChar - 'a']++;
                firstChar = s2.charAt(i);
            }

            if (canCover(charCountArr, charArrS1)) {
                System.out.print(i);
                return;
            }
        }
        // 遍历完都没有找到满足条件的子串
        System.out.print("-1");
        return;
    }

    // arr 中每个字母出现的次数,不小于 s1 中对应字母出现的次数,就可以覆盖
    public static boolean canCover(int[] arr, int[] s1) {
        for (int i = 0; i < 26; i++) {
            if (arr[i] < s1[i]) {
                return false;
            }
        }
        // 遍历完成,说明成功覆盖
        return true;
    }
}

 

© 版权声明

相关文章

暂无评论

暂无评论...