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