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

2023年华为OD机考真题:字符串解密

算法刷题1年前 (2023)更新 江南白衣
316 0 0
2023年华为OD机考真题:字符串解密

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:字符串解密
知识点:数组字符串排序
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:给定两个字符串string1和string2。string1是一个被加扰的字符串。string1由小写英文字母(’a’~’z’)和数字字符(’0’~’9’)组成,而加扰字符串由’0’~’9’、’a’~’f’组成。string1里面可能包含0个或多个加扰子串,剩下可能有0个或多个有效子串,这些有效子串被加扰子串隔开。
string2是一个参考字符串,仅由小写英文字母(’a’~’z’)组成。
你需要在string1字符串里找到一个有效子串,这个有效子串要同时满足下面两个条件:
1)这个有效子串里不同字母的数量不超过且最接近于string2里不同字母的数量,即小于或等于string2里不同字母的数量的同时且最大。
2)这个有效子串是满足条件(1)里的所有子串(如果有多个的话)里字典序最大的一个。
如果没有找到合适条件的子串的话,请输出”Not Found”
示例:
输入字符串string1为”thisisanewday111forme”,输入字符串string2为”good”。string1里有效子串和加扰子串分割后可表示为:”thisis”+”a”+”n”+”e”+”w”+”da”+”y”+”111f”+”orm”+”e”,去除加扰子串(”a”、”e”、”da”、”111f”、”e”)后的有效子串候选为(“thisis”, “n”, “w”, “y”, “orm”)。输入字符串string2里不同字母的数量为3(’g’、’o’、’d’),从有效子串候选里可以找出”orm”满足要求,其不同字母的数量为3,最接近于string2不同字母的数量。
输入描述:
input_string1
input_string2
说明:输入为两个字符串,第1行是题目里的string1(被加扰的字符串),第2行是题目里的string2(参考字符串)
输出描述:
output_string
说明:输出为一个字符串(有效字符串)
补充说明:
输入字符串string1的长度在1~100000之间,string2的长度在1~500之间
示例1
输入:
123admyffc79pt
ssyy
输出:
pt
说明:
将输入字符串1里的加扰子串”123ad”、”ffc79″去除后得到有效子串序列:”my”、”pt”,其中”my”里不同字母的数量为2(有’m’和’y’两个不同字母),”pt”里不同字母的数量为2(有’p’和’t’两个不同字母);输入字符串2里不同字母的数量为2(有’s’和’y’两个不同字母)。
可得到最终输出结果为”pt”,其不同字母的数量最接近于”ssyy”里不同字母的数量的同时字典序最大。
示例2
输入:
123admyffc79ptaagghi2222smeersst88mnrt
ssyyfgh
输出:
mnrt
说明:
将输入字符串1里的加扰子串”123ad”、”ffc79″、”aa”、”2222″、”ee”、”88″去除后得到有效子串序列:”my”、”pt”、”gghi”、”sm”、”rsst”、”mnrt”;输入字符串2里不同字母的数量为5(有’s’、’y’、’f’、’g’、’h’ 5个不同字母)。
可得到最终输出结果为”mnrt”,其不同字母的数量(为4)最接近于”ssyyfgh”里不同字母的数量,其他有效子串不同字母的数量都小于”mnrt”。
示例3
输入:
abcmnq
rt
输出:
Not Found
说明:
将输入字符串1里的加扰子串”abc”去除后得到有效子串序列:”mnq”;输入字符串2里不同字母的数量为2(有’r’、’t’两个不同的字母)。
可得到最终的输出结果为”Not Found”,没有符合要求的有效子串,因有效子串的里不同字母的数量(为3),大于输入字符串2里的不同字母的数量
解题思路:
根据题意:string1的子串要求:
1、只包含字母 g – z
2、且子串中不同字母的数量小于等于string2中的不同字母数量
求字符串中不同字母数量可以使用set,set可以去重,set的长度则为不同字母的数量。

代码实现一:

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 字符串解密
 * @Description 给定两个字符串string1和string2。string1是一个被加扰的字符串。
 * string1由小写英文字母('a'~'z')和数字字符('0'~'9')组成,而加扰字符串由'0'~'9'、'a'~'f'组成。
 * string1里面可能包含0个或多个加扰子串,剩下可能有0个或多个有效子串,这些有效子串被加扰子串隔开。
 * string2是一个参考字符串,仅由小写英文字母('a'~'z')组成。
 * @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 string1 = sc.nextLine();
        String string2 = sc.nextLine();
        String temp = "";
        List<String> list = new ArrayList<>();  //符合要求的字符串集合
        int max = 0;
        int diffLen = length(string2);  //string2不同字母的数量
        for (int i = 0; i < string1.length(); i++) {
            char c = string1.charAt(i);
            if (c >= 'g' && c <= 'z') {   //g到z属于有效字母
                temp += c;
                if (i != string1.length() - 1) continue;     //需要考虑最后一个字母
            }
            if (!temp.equals("")) {
                int len = length(temp);     //子串中不同字母的数量
                if (len <= diffLen && len >= max) {     //数量必须要小于等于string2的不同字母数量
                    if (len > max) {
                        list.clear();       //有更接近string2的不同字母数量,清除list
                    }
                    max = Math.max(max, len);  //更新max值
                    list.add(temp);
                }
                temp = "";     //temp已处理,需要置空
            }
        }
        Collections.sort(list);
        System.out.println(list.size() == 0 ? "Not Found" : list.get(list.size() - 1));
    }

    /**
     * 求字符串中不同字母的数量
     * @param s
     * @return
     */
    public static int length(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            set.add(c);
        }
        return set.size();
    }

}

代码实现二:

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

/**
 * @title 字符串解密
 * @Description 给定两个字符串string1和string2。string1是一个被加扰的字符串。
 * string1由小写英文字母('a'~'z')和数字字符('0'~'9')组成,而加扰字符串由'0'~'9'、'a'~'f'组成。
 * string1里面可能包含0个或多个加扰子串,剩下可能有0个或多个有效子串,这些有效子串被加扰子串隔开。
 * string2是一个参考字符串,仅由小写英文字母('a'~'z')组成。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static String an() {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        HashSet<String> set = new HashSet<>();

        for (char c : s2.toCharArray()) {
            set.add(c + "");
        }

        String sub = "1234567890abcdef";
        int index = 0;
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (sub.contains(s1.charAt(i) + "")) {
                list.add(s1.substring(index, i));
                index = i + 1;
            } else {
                if (i == s1.length() - 1) {
                    list.add(s1.substring(index));
                }
            }
        }

        String end = "";
        for (int i = 0; i < list.size(); i++) {
            String cs = list.get(i);
            if (cs.length() > 0) {
                HashSet<String> cset = new HashSet<>();
                for (int j = 0; j < cs.length(); j++) {
                    cset.add(cs.charAt(j) + "");
                }
                int len = cset.size();

                if (len <= set.size()) {
                    HashSet<String> sset = new HashSet<>();
                    for (int j = 0; j < end.length(); j++) {
                        sset.add(end.charAt(j) + "");
                    }
                    int sslen = sset.size();
                    if (len > sslen) {
                        end = cs;
                    } else if (len == sslen && cs.compareTo(end) > 0) {
                        end = cs;
                    }
                }
            }
        }
        if (end.length() > 0) {
            return end;
        } else {
            return "Not Found";
        }
    }

    public static void main(String[] args) {
        String answer = an();
        System.out.println(answer);
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...