全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：知识图谱新词挖掘1
知识点滑窗
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。
新词挖掘：给出一个待挖掘文本内容字符串Content和一个词的字符串word，找到content中所有word的新词。
新词：使用词word的字符排列形成的字符串。
请帮小华实现新词挖掘，返回发现的新词的数量。
输入描述：
第一行输入为待挖掘的文本内容content；
第二行输入为词word；
输出描述：
在中找到的所有word的新词的数量。
补充说明：
0<=content的长度<=10000000；
1=<word的长度<=2000
示例1
输入：
qweebaewqd
qwe
输出：
2
说明：
起始索引等于 0 的子串是 “qwe”, 它是 word的新词。
起始索引等于 6 的子串是 “ewq”, 它是 word 的新词。
示例2
输入：
abab
ab
输出：
3
说明：
起始索引等于 0 的子串是 “ab”, 它是 word的新词。
起始索引等于 1 的子串是 “ba”, 它是 word的新词。
起始索引等于 2 的子串是 “ab”, 它是 word的新词。
解题思路：
1、先对word进行字符排序
2、设定一个滑窗，left=0, right=word.length()
3、对截取的字符串进行字符排序，得出的eqw跟word排序后的字符一致，则符合要求
4、左右滑窗都进行右移
5、对截取的字符串进行字符排序，得出的eqw跟word排序后的字符不一致，不符合要求
6、以此进行类推，得到ewq跟word排序后字符—致，符合要求
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 知识图谱新词挖掘1
* @Description 小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。
* 新词挖掘：给出一个待挖掘文本内容字符串Content和一个词的字符串word，找到content中所有word的新词。
* 新词：使用词word的字符排列形成的字符串。
* 请帮小华实现新词挖掘，返回发现的新词的数量。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String content = sc.nextLine();
String word = sc.nextLine();
char[] charWord = word.toCharArray();
Arrays.sort(charWord); //将word转化为数组，并进行排序，方便进行判断
int left = 0; //滑窗左边界
int right = word.length(); //滑窗右边界
int count = 0; //满足新词挖掘的个数
while (right <= content.length()) {
String temp = content.substring(left, right);
char[] charTemp = temp.toCharArray();
Arrays.sort(charTemp);
boolean isTrue = true; //是否满足新词挖掘
for (int i = 0; i < charTemp.length; i++) {
if (charWord[i] != charTemp[i]) {
isTrue = false; //只要有一个值不一样就不符合
}
}
if (isTrue) {
count++;
}
left++;
right++;
}
System.out.println(count);
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 知识图谱新词挖掘1
* @Description 小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱。
* 新词挖掘：给出一个待挖掘文本内容字符串Content和一个词的字符串word，找到content中所有word的新词。
* 新词：使用词word的字符排列形成的字符串。
* 请帮小华实现新词挖掘，返回发现的新词的数量。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String stra = sc.nextLine();
String strb = sc.nextLine();
if (stra.length() < strb.length()) {
System.out.println(0);
return;
}
int count = 0;
char[] strbc = strb.toCharArray();
Arrays.sort(strbc);
int left = 0;
int right = strb.length() - 1;
while (right < stra.length()) {
String str = stra.substring(left, right + 1);
char[] strba = str.toCharArray();
Arrays.sort(strba);
if (check(strba, strbc)) {
count++;
}
left++;
right++;
}
System.out.println(count);
}
public static boolean check(char[] a, char[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
}
相关文章
