【华为OD题库-110】反转每对括号间的子串-java

2023-12-25 20:03:50

题目

给出一个字符串s(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。注意,您的结果中不应包含任何括号。
示例1:
输入: s = “(abcd)”
输出: “dcba”
示例2:
输入: s = “(u(love)i)”
输出: “iloveu”
解释: 先反转子字符串“love",然后反转整个字符串。
示例3:
输入: s = “(ed(et(oc))el)”
输出: “leetcode”
解释: 先反转子字符串"oc”,接着反转“etco”,然后反转整个字符串。
示例4:
输入: s = "a(bcdefghijkl(mno)p)q”
输出: “apmnolkjihgfedcbq”

思路

利用栈的先入后出特性,遇到),这将字符串翻转后重新入栈
最后栈中的数据就是要求的字符串,此时应该先入先出,外层可以用双端队列实现

题解

package hwod;

import java.util.LinkedList;
import java.util.Scanner;

public class ReverseSub {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(reverseSub(s));
    }

    private static String reverseSub(String s) {
        LinkedList<Character> queue = new LinkedList<>();
        LinkedList<Character> tmp = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                while (!queue.isEmpty()&&queue.peekLast() != '(') {
                    tmp.addLast(queue.removeLast());
                }
                if(!queue.isEmpty()) queue.removeLast();
                while (!tmp.isEmpty()) {
                    queue.addLast(tmp.removeFirst());
                }
            } else {
                queue.addLast(s.charAt(i));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            sb.append(queue.removeFirst());
        }
        return sb.toString();
    }
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。

说明

本专栏所有文章均为原创,欢迎转载,请注明文章出处:https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信,搜索请谨慎鉴别。技术类文章一般都有时效性,本人习惯不定期对自己的博文进行修正和更新,因此请访问出处以查看本文的最新版本。

文章来源:https://blog.csdn.net/qq_31076523/article/details/135205805
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。