全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：最多提取子串数目
知识点：字符串统计
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
现从字符串A中按规则挑选一些字母，可以组成字符串B。
挑选规则如下：
1） 同一个位置的字母只能被挑选一次
2） 被挑选字母的相对先后顺序不能改变
求最多可以同时从A中挑选多少组能组成B的字符串
输入描述：
输入为2行，第1行输入字符串A，第2行输入字符串B，行首行尾无多余空格
其中A、B均由[a-z] 26个英文小写字母组成
0<A.length<100，A中可能包含重复字母
0<B.length<10，B中不会出现重复字母
输出描述：
输出1行，包含1个数字，表示最多可以同时从A中挑选多少组能组成B的字符串
行末无多余空格
补充说明：
无需验证输入格式和输入数据合法性
示例1
输入：
badc
bac
输出：
1
说明：
从字符串A(“badc”)中可以按字母相对先后顺序取出字符串B(“bac”)
示例2
输入：
badc
abc
输出：
0
说明：
从字符串A(“badc”)中无法按字母相对先后顺序取出字符串B(“abc”)
示例3
输入：
aabbcxd
abcd
输出：
1
说明：
从字符串A(“aabbcxd”)中挑选一组B(“abcd”)后，A中剩余字符串为”abx”，无法再挑出”abcd”
示例4
输入：
ababcecfdc
abc
输出：
2
说明：
按如下步骤（步骤不唯一），可以同时从字符串A(“ababcecfdc”)中最多取出两个B(“abc”)，其中下划线标注的是每步提取的字母：
剩余的”efdc”无法继续提取”abc”，结果为2
示例5
输入：
aaa
a
输出：
3
说明：
从字符串A(“aaa”)中可以挑选3个字符串B(“a”)
解题思路：
如示例4：
父字符串：ababcecfdc 父索引indexF=0
子字符串：abc 子索引indexS=0
indexF=0, indexS=0 a == a;
indexF+1=1, indexS+1=1 b == b
indexF+1=2, indexS+1=2 a != c
indexF+1=3, indexS=2 b ! = c
indexF+1=4, indexS=2 c == c
满足子串 父字符串变为：ab ecfdc（匹配过的需要用空字符串替代）
indexF=0, indexS=0 a == a;
继续重复上面操作，直至indexF=父字符串长度-1
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 最多提取子串数目
* @Description 给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
* 现从字符串A中按规则挑选一些字母，可以组成字符串B。
* 挑选规则如下：
* 1） 同一个位置的字母只能被挑选一次
* 2） 被挑选字母的相对先后顺序不能改变
* 求最多可以同时从A中挑选多少组能组成B的字符串
* @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 strF = sc.nextLine(); //父字符串
String strS = sc.nextLine(); //子字符串
char[] chars = strF.toCharArray(); //将父字符串转化为数组
int indexF = 0; //父字符串索引
int indexS = 0; //子字符串索引
int count = 0; //符合的个数
while (indexF < strF.length()){
if(chars[indexF] == strS.charAt(indexS)){
chars[indexF] = ' '; //已经匹配的置为空
indexS++;
}
if(indexS == strS.length()){ //长度相同则表示符合子串
indexS = 0;
indexF = 0;
count++;
}else {
indexF++; //不符合则匹配下一个字符
}
}
System.out.println(count);
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 最多提取子串数目
* @Description 给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
* 现从字符串A中按规则挑选一些字母，可以组成字符串B。
* 挑选规则如下：
* 1） 同一个位置的字母只能被挑选一次
* 2） 被挑选字母的相对先后顺序不能改变
* 求最多可以同时从A中挑选多少组能组成B的字符串
* @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 stra = sc.nextLine();
char[] x = stra.toCharArray();
String strb = sc.nextLine();
int[] arrs = new int[stra.length()];
int index = 0;
int count = 0;
int i = 0;
while (i < stra.length()) {
if (x[i] == strb.charAt(index)) {
arrs[index] = i + 1;
index++;
x[i] = '0';
}
if (index == strb.length()) {
index = 0;
i = arrs[0];
count++;
} else {
i++;
}
}
System.out.print(count);
}
}
相关文章
