网站设计红色表示什么,广州电商运营培训哪个机构好,网页版微信二维码一直失效,有教做路桥质检资料的网站吗目录
题目部分
解读与分析
代码实现 题目部分
题目字符串解密题目说明给定两个字符串string1和string2。 string1是一个被加扰的字符串。string1由小写英文字母#xff08;a~z#xff09;和数字字符#xff08;0~9#xff09;组成#xff0c;而加扰字符串由0~9、a~f 组…目录
题目部分
解读与分析
代码实现 题目部分
题目字符串解密题目说明给定两个字符串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里有效子串和加扰子串分割后可表示为thisisanewday111forme去除加扰子串a、e、da、111f、e后的有效子串候选为(thisis, n, w, y, orm)。输入字符串string2里不同字母的数量为3g、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里的不同字母的数量。 解读与分析
题目解读
本题有 2 行输入第一行输入字符串的字符中字符的范围是 a~z 和 0 ~ 9在输入字符串中如果字符范围在 a~f 或 0 ~ 9 中那么这些字符是干扰字符可以理解为间隔符。这些间隔符把源字符串分割成了多个字符串。
第二行输入一个字符串统计出这个字符串中出现的唯一字符串个数设为 max即当同一个字母出现多次时只计算一次。
从第一行分隔出的多个字符串中过滤掉不同字母数大于 max 的字符串。在剩下的字符串中找出不同字母数最大的字符串如果字符串是唯一的输出它如果不同字母数最大的字符串存在多个输出字典序最大的那个如果不存在符合条件的字符串则输出 Not Found。
分析与思路
先设置 3 个变量 1. max整形变量。用于统计第二行输入字符串的唯一字符个数。 2. currentMax整形变量初始值为 0。在遍历过程中用于统计在分隔字符串时记录不同字母数不大于 max 的最大个数。 3. output字符串长度初始值为 Not Found。
算法如下 1. 遍历第二行字符串中的字母把所有字符放到一个 set 中最后统计 set 中元素的个数赋值给 max。为什么要先计算 max 值呢因为这样做可以减少统计的工作量。 先遍历第二行字符串在计算出 max 值之后再遍历第一行字符串时可以直接忽略掉分隔后长度大于 max 的字符串。否则需要先统计分隔后的所有字符串无论长度是多少最后还是要过滤掉长度大于 max 的字符串多了些不必要的工作量。2. 遍历第一行字符串中的字母根据干扰字母分隔符把它分隔成若干字符串。对于遍历过程中的每个字符串进行如下操作 ① 如果此字符串的不同字母数大于 max则舍弃它。 ② 如果此字符串的不同字母数小于 currentMax舍弃它。 ③ 如果此字符串的不同字母数大于 currentMax把此字符串不同字母数赋值给 currentMax并把此字符串赋值给 output。 ④ 如果此字符串的不同字母数等于 currentMax比较此字符串与 output 的字典序大小如果此字符串的字典序较大则更新 output 的值为此字符串。 3. 遍历完字第一行字符串后输出 output。
此算法只需要遍历一次字符串时间复杂度为 o(n)。在遍历过程中仅需要 3 个临时变量空间复杂度为 o(1)。 代码实现
Java代码
import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;/*** 字符串解密* * since 2023.09.07* version 0.1* author Frank**/
public class StringDecrypt {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String firstLine sc.nextLine();String secondLine sc.nextLine();processStringDecrypt(firstLine, secondLine);}}private static void processStringDecrypt(String firstLine, String secondLine) {int max getUniqueCount(secondLine);int currentMax 0;String output Not Found;Character[] fiterChars { a, b, c, d, e, f, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };SetCharacter filterSet new HashSetCharacter(Arrays.asList(fiterChars));int i 0;while (i firstLine.length()) {Character first firstLine.charAt( i );if( filterSet.contains( first ) ){i ;continue;}int leftIndex i;int rightIndex i; // 不包含Character iterChar firstLine.charAt( i );while( !filterSet.contains( iterChar )){i ;if( i firstLine.length() ){rightIndex i;break;}iterChar firstLine.charAt( i );}rightIndex i;String subStr firstLine.substring( leftIndex, rightIndex );int subStrUniCnt getUniqueCount( subStr );if( subStrUniCnt 0 || subStrUniCnt currentMax || subStrUniCnt max ){continue;}if( subStrUniCnt currentMax ){currentMax subStrUniCnt;output subStr;continue;}// subStrLength currentMaxif( output.compareTo( subStr ) 0 ){output subStr;continue;}}System.out.println(output);}private static int getUniqueCount(String secondLine) {SetCharacter charSet new HashSetCharacter();for (int i 0; i secondLine.length(); i) {charSet.add(secondLine.charAt(i));}return charSet.size();}}
JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {var firstLine line;var secondLine await readline();processStringDecrypt(firstLine, secondLine);}}();function processStringDecrypt(firstLine, secondLine) {var max getUniqueCount(secondLine);var currentMax 0;var output Not Found;var filterSet new Set([a, b, c, d, e, f, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);var i 0;while (i firstLine.length) {var first firstLine.charAt(i);if (filterSet.has(first)) {i;continue;}var leftIndex i;var rightIndex i; // 不包含var iterChar firstLine.charAt(i);while (!filterSet.has(iterChar)) {i;if (i firstLine.length) {rightIndex i;break;}iterChar firstLine.charAt(i);}rightIndex i;var subStr firstLine.substring(leftIndex, rightIndex);var subStrUniCnt getUniqueCount(subStr);if (subStrUniCnt 0 || subStrUniCnt currentMax || subStrUniCnt max) {continue;}if (subStrUniCnt currentMax) {currentMax subStrUniCnt;output subStr;continue;}// subStrLength currentMaxif (output subStr) {output subStr;continue;}}console.log(output);
}function getUniqueCount(secondLine) {var charSet new Set();for (var i 0; i secondLine.length; i) {charSet.add(secondLine.charAt(i));}return charSet.size;
}
(完)
