全网最全面的华为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; } }