当前位置: 首页 > backend >正文

左右括号的最小处理次数

1、题目描述

多多君在处理一个由左结号(和右语号)组成的字符串,多多君每次处理时可以顺序读取一个字符或者一个有效括号子串,求问多多的最小处理次数。


输入描述:

第一行为一个整数N,表示字符串长度(1<=N<=10000),
第二行输入为一个长度为N的字符串,字符串由( 和 )组成


输出描述:

输出一个整数,表示字符串的最小处理次数

补充说明:

有效括号子串需要满足:
1.括号成对闭合,每个"("都有一个对应的")"
2.正确嵌套顺序:右括号不能出现在对应的左括号之前
例如:“()”,“()()”“(()())”均有效括号子串,“)(”, "(()","()())"不是有效括号


实例1:

输入:
4
))))
输出
4
说明
每个字符需要单独处理,需要处理4次


实例2:

输入:
6
((()))
输出:
1
说明
((()))为有效括号子串,需要处理1次
 

 2、解题思路

要解决这个问题,我们需要找到处理给定括号字符串的最小次数。每次处理可以是一个单独的字符或一个有效的括号子串。有效括号子串的定义是成对闭合且正确嵌套的括号序列。

  1. 有效括号子串识别:利用栈来识别有效的括号子串。遍历字符串,遇到左括号时压栈,遇到右括号时弹出栈顶的左括号,并记录有效子串的位置。

  2. 处理次数计算:未被包含在任何有效子串中的字符需要单独处理。有效子串可以一次性处理,因此处理次数等于未被覆盖的字符数加上有效子串的数量。

代码实现

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();String s = scanner.next();System.out.println(minProcessingTimes(s));}public static int minProcessingTimes(String s) {Stack<Integer> stack = new Stack<>();boolean[] matched = new boolean[s.length()];// 标记所有匹配的括号对for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {  //遇到(就入栈stack.push(i);} else if (!stack.isEmpty()) {  //遇到),且栈不为空,就弹出栈顶元素,并记录有效位置matched[stack.pop()] = true;  //栈顶字符(的位置记为true,且)位置也记为truematched[i] = true;}}int count = 0;int i = 0;while (i < s.length()) {if (matched[i]) {count++; // 处理一个有效子串while (i < s.length() && matched[i]) {i++; // 跳过已匹配的字符}} else {count++; // 处理单个字符i++;}}return count;}

代码解释

  1. 栈的使用:遍历字符串,使用栈来匹配有效的括号对。遇到左括号时压栈,遇到右括号时弹出栈顶的左括号,并标记这两个位置为已匹配。

  2. 处理次数计算:遍历标记数组,连续的已匹配字符视为一个有效子串,只需一次处理;未匹配的字符需要单独处理。

  3. 时间复杂度:O(N),其中N是字符串的长度。每个字符仅被处理一次,栈操作也是线性时间。

http://www.xdnf.cn/news/5466.html

相关文章:

  • Redis 基础详解:从入门到精通
  • 本贴会成为记录贴
  • 如何读懂《纯粹理性批判》
  • 【软件测试】基于项目驱动的功能测试报告
  • Java在人工智能中的应用:机器学习与深度学习技术探讨
  • 详解SLAM中的李群和李代数(中)
  • HCIP-BGP实验一
  • Quartus与Modelsim-Altera使用手册
  • JavaSE核心知识点02面向对象编程02-08(异常处理)
  • 常见的会触发 Shuffle 的操作和方法
  • 时序约束高级进阶使用详解四:Set_False_Path
  • 学习黑客5 分钟小白弄懂Windows Desktop GUI
  • win10-django项目连接本地mysql
  • 系统思考:个人与团队成长
  • BGP实验练习1
  • Linux系统编程之消息队列
  • 如何重启pycharm中的项目?
  • 基于STM32单片机设计的教室节能照明系统
  • HTML5表格语法格式详解
  • 用浏览器打开pdf,如何使用划词翻译?
  • MySQL 数据操纵与数据库优化
  • tensorflow 1.x
  • 架构思维:通用架构模式_怀疑下游的设计思路与最佳实践
  • 利用“Flower”实现联邦机器学习的实战指南
  • html body 设置heigth 100%,body内元素设置margin-top出滚动条(margin 重叠问题)
  • 从零到精通:探索 GoFrame 框架的 SSE 优势与实战经验
  • 进程(沉淀中)
  • 运动员技术等级分为国际级运动健将
  • uniapp-商城-52-后台 商家信息(商家信息数据,云对象使用)
  • Java学习手册:服务注册与发现