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

2023年华为OD机考真题:知识图谱新词挖掘1

算法刷题1年前 (2023)更新 江南白衣
517 0 0
2023年华为OD机考真题:知识图谱新词挖掘1

全网最全面的华为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排序后字符—致,符合要求

2023年华为OD机考真题:知识图谱新词挖掘1

代码实现一:

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;
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...