网站开发 用户角色,wordpress站文章显示时分秒,wordpress主题调度,河南民基建设工程有限公司网站目录
题目部分
解读与分析
代码实现 题目部分
题目字符串化繁为简题目说明给定一个输入字符串#xff0c;字符串只可能由英文字母 (a~z、A~Z )和左右小括号 ((、))组成。当字符里存在小括号时#xff0c;小括号是成对的#xff0c;可以有一个或多个小括号对#xff0c;…目录
题目部分
解读与分析
代码实现 题目部分
题目字符串化繁为简题目说明给定一个输入字符串字符串只可能由英文字母 (a~z、A~Z )和左右小括号 ((、))组成。当字符里存在小括号时小括号是成对的可以有一个或多个小括号对小括号对不会嵌套小括号对内可以包含1个或多个英文字母也可以不包含英文字母。当小括号对内包含多个英文字母时这些字母之间是相互等效的关系而且等效关系可以在不同的小括号对之间传递即当存在a和b等效和存在b和c 等效时a 和 c 也等效另外同一个英文字母的大写字母和小写字母也相互等效 (即使它们分布在不同的括号对里)。 需要对这个输入字符串做简化输出一个新的字符串输出字符串里只需保留输入字符串里的没有被小括号对包含的字符(按照输入字符串里的字符顺序) 并将每个字符替换为在小括号对里包含且字典序最小的等效字符。 如果简化后的字符串为空请输出为0。 示例: 输入字符串为never(dont)give(run)up(f)()初始等效字符集合为(d,o,n,t)、(r,u,n)由于等效关系可以传递因此最终等效字符集合为(d,o,n,t,r,u)将输入字符串里的剩余部分按字典序最小的等效字符替换后得到devedgivedp。输入描述input_string 输入为 1 行代表输入字符串。输出描述output_string 输出为 1 行代表输出字符串。补充说明输入字符串的长度在 1 ~ 100000 之间。-----------------------------------------------------------示例示例1输入()abd输出abd说明输入字符串里没有被小括号包含的子字符串为abd其中每个字符没有等效字符输出为abd。示例2输入(abd)demand(fb)for输出aemanaaor说明等效字符集为(a,b,d,f)输入字符串里没有被小括号包含的子字符串集合为 demandfor将其中字符替换为字典序最小的等效字符后输出为aemanaaor。示例3输入()happy(xyz)new(wxy)year(t)输出happwnewwear说明等效字符集为(x,y,z,w)输入字符串里没有被小括号包含的子字符串集合为happynewyear将其中字符替换为字典序最小的等效字符后输出为happwnewwear。示例4输入()abcdefgAC(a)(Ab)(C)输出AAcdefgAC说明等效字符集为(a,A,b)输入字符里没有被小括号包含的子字符串集合为abcdefgAC将其中字符替换为字典序最小的等效字符后输出为AAcdefgAC。 解读与分析
题目解读
本题的输入和输出都是一段字符串。输出字符串在输入字符串的基础上进行精简精简按要求如下
1. 忽略输入字符串中所有使用小括号包裹起来的子字符串 例如如果输入字符串为 abc(xxx)def(xxxx)那么先去掉括号的部分把字符串转换成中间字符串 abcdef再进行后续操作。 2. 对于所有小括号对中所包含的字符构建等效字符集构建等效字符集的规则参见“分析与思路”部分。一个字符集中所有的字符等效某个字母这个字母是字符集中字典序最小的那个字母。 例如某个有效字符集是 A, a, b在这个字符集的 3 个字母中字典序最小的字母是 A所以当碰到这 3 个字母中任意一个时一律转换成 A。
需要注意两点 1. 输入字符串中的等效字符集可能有多个。 2. 相同英文字母的大写和小写视作等效字符。
分析与思路
设源输入的字符串为 sourceStr接下来字符串精简可以分两步实现
1. 遍历 sourceStr在遍历过程中进行如下操作。 ① 去掉 sourceStr 中括号对包含的部分生成中间字符串 tmpStr。 ② 构建等效字符集具体算法稍后说明并算出每个字符集等效的字母即等效字符集中字典序最小的那个字母。创建一个map命名为 charSetMap在遍历 sourceStr 过程中用于建立字符key和其所在的字符集value之间的关系。
2. 遍历完 sourceStr构建好字符集后进行如下操作。 ① 创建一个 map命名为 setTarCharMap用于存储字符集key和其等效的字母value之间的关系。 ② 创建一个 map命名为 charSrcTarMap在 charSetMap 和 setTarCharMap 基础上建立需要转换的字符key和最终转换的字符value之间的关系。 3. 遍历中间字符串 tmpStr设最终字符串为 tarStr。遍历字符时判断此字符是否在charSrcTarMap中存在key如存在则替换成这个 key 所对应的 value加到 tarStr 的末尾否则原封不动地加到 tarStr 末尾。
最终 tarStr 的结果为精简后的字符串。
-----------------------------------------------------------
在以上的实现中第 1 步中的关键步骤 构建等效字符集 写得比较粗略下面详解构建等效字符集的步骤
1. 创建一个 map命名为 charSetMap其 key 为等效字符集中的字符value 为字符 set用于存储 key 所在的结合。 举例说明如果存在 2 个等效字符集a, b, c{d, e}那么 charSetMap 有 5 个 key分别为 a、b、c、d、e。其中a、b、c 这 3 个 key 所对应的 value 为 seta, b, c另外 2 个 key 对应的 value 为 set {d,e}。
2. 遍历字符串 srcStr每碰到一个括号对时提取出括号对中的所有字符放到数组 tmpCharArr 中。遍历 tmpCharArr检查 tmpCharArr 中的字符是否是 charSetMap 的key 如果 ① tmpCharArr 中所有的字符都不是 charSetMap 的 key则意味着 tmpCharArr 中的所有字符与已存在的等效字符集不存在交集那么构建一个 set设为 tmpSettmpSet 中包含 tmpCharArr 的所有字符。遍历 tmpCharArr把 tmpCharArr 的元素作为 key 添加到 charSetMap其对应的 value 为刚创建的 tmpSet。 ② tmpCharArr 中至少有一个字符是 charSetMap 的 key此时可能存在等效字符集合并的情况。 · 遍历 tmpCharArr 时当碰到第一个字符假设为 tmpChar是 charSetMap 的 key 时设 set1 为 charSetMap.get( tmpChar )。 · 继续遍历 tmpCharArr如果下一个字符假设为 char2不是 charSetMap 的 key那么把 char2 添加到 set1 中并把 char2, set1 添加到 charSetMap 中。 · 继续遍历 tmpCharArr如果下一个字符假设为 char3是 charSetMap 的 key并且 charSetMap.get( char3) set1则意味着 char3 已经在 set1 中跳过。 · 继续遍历 tmpCharArr如果下一个字符假设为 char4是 charSetMap 的 key并且 charSetMap.get( char4) ! set1设 set2 charSetMap.get( char4 )则需要把 set2 合并到 set1 中。把 set2 中所有的元素添加到 set1 中并把 set2 中所有字符作为 key 添加到 charSetMap 中它们对应的 value 为 set2。
遍历完字符串 srcStr 之后等效字符集构建完毕。
此算法需要遍历 2 次字符串其时间复杂度为 o(n)由于字母个数有限创建的各种 map 包含的元素都很有限额外的辅助空间与字符串长度无关空间复杂度为 o(1)。 代码实现
Java代码
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;/*** 字符串化繁为简* * since 2023.09.06* version 0.1* author Frank*/
public class StringSimplify {public static void main(String[] args) {Scanner sc new Scanner(System.in);// 第一行输入一串数字以空格分隔String sourceStr sc.nextLine();StringBuffer sb new StringBuffer();// 第一次遍历 sourceStrint i 0;MapCharacter, SetCharacter charSetMap new HashMapCharacter, SetCharacter();while (i sourceStr.length()) {int leftPT sourceStr.indexOf((, i);int rightPT sourceStr.indexOf(), i);// 没有小括号了if (leftPT -1 rightPT -1) {sb.append(sourceStr.substring(i));break;}// 把 i 和 左括号之间部分加到sb。sb.append(sourceStr.substring(i, leftPT));String setStr sourceStr.substring(leftPT 1, rightPT);if (setStr.length() 0) {// 构建 charSetMapconstructCharSetMap(charSetMap, setStr);}i rightPT 1;}MapSetCharacter, Character setTarCharMap new HashMapSetCharacter, Character();constructSetTarCharMap(charSetMap, setTarCharMap);MapCharacter, Character charSrcTarMap new HashMapCharacter, Character();constructCharSrcTarMap(charSetMap, setTarCharMap, charSrcTarMap);String ret getReplacedString(charSrcTarMap, sb.toString());if( ret.length() 0 ){ret 0;}System.out.println(ret);}private static String getReplacedString(MapCharacter, Character charSrcTarMap, String tmpStr) {StringBuffer sb new StringBuffer();for (int i 0; i tmpStr.length(); i) {Character curChar tmpStr.charAt(i);Character tarChar charSrcTarMap.get(curChar);if (tarChar ! null) {sb.append(tarChar);} else {sb.append(curChar);}}return sb.toString();}private static void constructCharSrcTarMap(MapCharacter, SetCharacter map,MapSetCharacter, Character setTarCharMap, MapCharacter, Character charSrcTarMap) {map.forEach((key, value) - {SetCharacter tmpValue map.get(key);Character finalValue setTarCharMap.get(tmpValue);charSrcTarMap.put(key, finalValue);});}private static SetCharacter getValueByIgnoreKey(MapCharacter, SetCharacter map, Character key) {SetCharacter ret map.get(key);if (ret ! null) {return ret;}Character newKey;if (Character.isLowerCase(key)) {newKey Character.toUpperCase(key);} else {newKey Character.toLowerCase(key);}return map.get(newKey);}private static void constructSetTarCharMap(MapCharacter, SetCharacter map,MapSetCharacter, Character setTarCharMap) {CollectionSetCharacter allSets map.values();for (IteratorSetCharacter iter allSets.iterator(); iter.hasNext();) {SetCharacter curSet iter.next();Character firstChar getSetFirstChar(curSet);setTarCharMap.put(curSet, firstChar);}}private static Character getSetFirstChar(SetCharacter curSet) {Character ret null;for (IteratorCharacter iter curSet.iterator(); iter.hasNext();) {Character curChar iter.next();if (ret null) {ret curChar;} else if (curChar ret) {ret curChar;}}return ret;}private static void constructCharSetMap(MapCharacter, SetCharacter map, String setStr) {int inMapCnt 0;SetCharacter set1 null;for (int i 0; i setStr.length(); i) {Character curChar setStr.charAt(i);if (getValueByIgnoreKey(map, curChar) ! null) {inMapCnt;if (inMapCnt 1) {set1 getValueByIgnoreKey(map, curChar);}}}if (inMapCnt 0 || inMapCnt 1) {// 全都不在map中则新建一个 set并放到map中。// inMapCnt 1, 放到初始化的 set1中。if (inMapCnt 0) {set1 new HashSetCharacter();}for (int i 0; i setStr.length(); i) {Character curChar setStr.charAt(i);set1.add(curChar);map.put(curChar, set1);}return;}// inMapCnt 2的情况所有的值都合并到 set1 中。for (int i 0; i setStr.length(); i) {Character curChar setStr.charAt(i);set1.add(curChar);SetCharacter set2 getValueByIgnoreKey(map, curChar);if (set2 null) {map.put(curChar, set1);continue;} else if (set1 set2) {continue;}// 把 set2 合并到 set1 中for (IteratorCharacter iter set2.iterator(); iter.hasNext();) {Character charInSet2 iter.next();set1.add(charInSet2);map.put(charInSet2, set1);}}}
}这题的逻辑处理并不复杂但代码量有些多近 170 行耗费了整整 1 个小时。如果是在考试中我未必有足够的时间完成它。
JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {let input [];while (line await readline()) {input.push(line);}var sourceStr input[0];var output ;// 第一次遍历 sourceStrvar i 0;var charSetMap new Map();while (i sourceStr.length) {var leftPT sourceStr.indexOf((, i);var rightPT sourceStr.indexOf(), i);// 没有小括号了if (leftPT -1 rightPT -1) {output sourceStr.substring(i);break;}// 把 i 和 左括号之间部分加到sb。output sourceStr.substring(i, leftPT);var setStr sourceStr.substring(leftPT 1, rightPT);if (setStr.length 0) {// 构建 charSetMapconstructCharSetMap(charSetMap, setStr);}i rightPT 1;}var setTarCharMap new Map();constructSetTarCharMap(charSetMap, setTarCharMap);var charSrcTarMap new Map();constructCharSrcTarMap(charSetMap, setTarCharMap, charSrcTarMap);var ret getReplacedString(charSrcTarMap, output);if( ret.length 0 ){ret 0;}console.log(ret);function getReplacedString(charSrcTarMap, tmpStr) {var sb ;for (var i 0; i tmpStr.length; i) {var curChar tmpStr.charAt(i);var tarChar charSrcTarMap.get(curChar);if (tarChar ! null) {sb tarChar;} else {sb curChar;}}return sb;}function constructCharSrcTarMap(map, setTarCharMap, charSrcTarMap) {map.forEach(function(value, key, thisMap) {var finalValue setTarCharMap.get(value);charSrcTarMap.set(key, finalValue);});}function getValueByIgnoreKey(map, key) {var ret map.get(key);if (ret ! null) {return ret;}var newKeyCode;if (key a key z) {// 小写字母转换成大写newKeyCode A.charCodeAt() (key.charCodeAt() - a.charCodeAt());} else {newKeyCode a.charCodeAt() (key.charCodeAt() - A.charCodeAt());}return map.get(String.fromCharCode(newKeyCode));}function constructSetTarCharMap(map, setTarCharMap) {map.forEach(function(item) {var firstChar getSetFirstChar(item);setTarCharMap.set(item, firstChar);});}function getSetFirstChar(curSet) {var ret null;curSet.forEach(function(curChar) {if (ret null) {ret curChar;} else if (curChar ret) {ret curChar;}});return ret;}function constructCharSetMap(map, setStr) {var inMapCnt 0;var set1 null;for (var i 0; i setStr.length; i) {var curChar setStr.charAt(i);if (getValueByIgnoreKey(map, curChar) ! null) {inMapCnt;if (inMapCnt 1) {set1 getValueByIgnoreKey(map, curChar);}}}if (inMapCnt 0 || inMapCnt 1) {// 全都不在map中则新建一个 set并放到map中。// inMapCnt 1, 放到初始化的 set1中。if (inMapCnt 0) {set1 new Set();}for (var i 0; i setStr.length; i) {var curChar setStr.charAt(i);set1.add(curChar);map.set(curChar, set1);}return;}// inMapCnt 2的情况所有的值都合并到 set1 中。for (var i 0; i setStr.length; i) {var curChar setStr.charAt(i);set1.add(curChar);var set2 getValueByIgnoreKey(map, curChar);if (set2 null) {map.set(curChar, set1);continue;} else if (set1 set2) {continue;}set2.forEach(function(value) {set1.add(value);map.set(value, set1);})}}}();
(完)
