新乡电子商务网站建设,济南口碑最好的装修公司,网站备案,漳州港建设规划局网站题目 给定一个输入字符串#xff0c;字符串只可能由英文字母(a ~ z、A ~ Z)和左右小括号()组成。当字符里存在小括号时#xff0c;小括号是成对的#xff0c;可以有一个或多个小括号对#xff0c;小括号对不会嵌套#xff0c;小括号对内可以包含1个或多个英文字母也可以不…题目 给定一个输入字符串字符串只可能由英文字母(a ~ z、A ~ Z)和左右小括号()组成。当字符里存在小括号时小括号是成对的可以有一个或多个小括号对小括号对不会嵌套小括号对内可以包含1个或多个英文字母也可以不包含英文字母。当小括号对内包含多个英文字母时这些字母之间是相互等效的关系而且等效关系可以在不同的小括号对之间传递即当存在a和b等效和存在b和c等效时a和c 也等效另外同一个英文字母的大写字和小写字母也相互等效(即使它们分布在不同的括号对里)。 要对这个输入字符串做简化输出一个新的字符串输出字符串里只需保留输入字符串里的没有被小括号对包含的字符(按照输入字符串里的字符顺序)并将每个字符替换为在小括号对里包含的字典序最小的等效字符。如果简化后的字符串为空请输出为0 示例输入字符串为never(dont)live(run)up(f)()“初始等效字符集合为(d,o,n,t,r,u,n)由于等效关系可以传递因此最终等效字符集合为(d,n,o,r,t,u)将输入字符串里的剩余部分按字典序最小的等效字符替换后得到devedlivedp” 输入描述 input string 输入为1行代表输入字符串 输出描述 output string 输出为1行代表输出字符串 备注 输入字符串的长度在1~100000之间 示例1: 输入∶ ()abd 输出: abd 说明: 输入字符串里没有被小括号包含的字符串为abd其中每个字符没有等效字符输出为abd 示例2: 输入∶ (abd)demand(fb)()for 输出: aemanaaor 说明: 等效字符集为(abd f)输入字符串里没有被小括号包含的字符串集合为demandfor”将其中字符替换为字典序最小的等效字符后输出为:“aemanaaor” 示例3: 输入∶ happy(xyz)new(wxy)year(t) 输出: happwnewwear 说明: 等效字符集为(w,x,y,z)输入字符串里没有被小括号包含的字符串集合为happynewyear”将其中字符替换为字典序最小的等效字等后输出为:“happwnewwear” 思路 比如输入的字符串为NeVeD(dont)Live(Drun)up(f)() 按照题意 先提取小括号括号内字符数大于1里的字符dontDrun去重后为dDontru。由于大小写是等效的所以这里如果转为全小写并去重排序后的结果为dnortu。于是现在需要将原来字符串中的dnortu全部转为d。得到字符串deVedLivedp 但是当我们全转为大写时将原来字符串中的dnortu全部转为D得到结果DeVeDLiveDp 题目应该是对输出字符串是忽略大小写的否则按照不同方式处理会得到不同的结果。 解题思路如下 首先提取小括号内的字符放入set中去重小括号内字符个数大于1时才放入set将其他字符非小括号内的字符组成新字符串newStr对set中的字符按照字典序排序并转为字符数组chars对newStr中遍历当某个字符出现在chars中时将它替换为chars[0]最后输出newStr即可 关键在于第1、2步即将输入字符串分离为括号内字符和括号外字符两部分 我们可以使用栈stack来实现使用sbStringBuilder存放括号外的字符使用set存放括号内的字符将输入字符串转为chars数组遍历chars 如果stack为空时说明没有出现括号直接把字符加入sb如果stack不为空或者字符串为时说明已经出现了括号或者第一次出现括号直接把字符加入stack如果遇到 代表一对括号结束应该清除stack。并且还需要根据括号对中的字符数量判断是否加入set中。怎么判断数量此时stack中的字符为(、若干字符stack.size-1如果字符数量大于1那么应该将stack中除最后一个(外的字符加入set。 最后考虑特殊情况比如按照括号对分离后sb为空直接输出0set为空则直接输出sb.toString() 题解
package hwod;import java.util.*;public class StringSimplifying {public static void main(String[] args) {Scanner sc new Scanner(System.in);String str sc.nextLine();System.out.println(stringSimplifying(str));}private static String stringSimplifying(String str) {SetCharacter set new HashSet();//存储括号内的字符StringBuilder sb new StringBuilder();//存储括号外的字符LinkedListCharacter queue new LinkedList();for (int i 0; i str.length(); i) {if (str.charAt(i) )) {if (queue.size() - 1 1) {while (queue.size() 1) {set.add(Character.toLowerCase(queue.pollLast()));//大小写等效全转为小写}}queue.clear();continue;}if (str.charAt(i) ( || !queue.isEmpty()) {queue.addLast(str.charAt(i));continue;}sb.append(str.charAt(i));}if (sb.length() 0) {return 0;}if (set.size() 0) {return sb.toString();}ArrayListCharacter chars new ArrayList(set);Collections.sort(chars);final char[] newChars sb.toString().toCharArray();for (int i 0; i newChars.length; i) {if (chars.contains(Character.toLowerCase(newChars[i]))) {newChars[i] chars.get(0);}}return String.valueOf(newChars);}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
