【九度】题目1342:寻找最长合法括号序列II(25分)

2024-08-25 12:32

本文主要是介绍【九度】题目1342:寻找最长合法括号序列II(25分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目地址:http://ac.jobdu.com/problem.php?pid=1342
题目描述:
假如给你一个由’(‘和’)’组成的一个随机的括号序列,当然,这个括号序列肯定不能保证是左右括号匹配的,所以给你的任务便是去掉其中的一些括号,使得剩下的括号序列能够左右括号匹配且长度最长,即最长的合法括号序列。
输入:
测试数据包括多个,每个测试数据只有一行,即一个随机的括号序列,该括号序列的长度保证不超过106。
输出:
对于每个测试案例,输出一个整数,表示最后剩下的最长合法括号序列长度。
样例输入:
(())()
(()
样例输出:
6
2
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-8065-1-1.html
解题思路:
这个是校验括号是否匹配,这个很简单,用栈去模拟。发现是左括号就入栈,发现是右括号,而且和左括号匹配就出栈。
同时,总长度+2。扫描一遍结束就是答案。
Java AC

import java.util.Scanner;
import java.util.Stack;public class Main {/** 1342*/public static void main(String[] args) throws Exception {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {String a = scanner.next();char array[] = a.toCharArray();int num = 0;Stack<Character> stack = new Stack<Character>();for (int i = 0; i < array.length; i++) {if (array[i] == '(') {stack.push(array[i]);}else if (array[i] == ')' && !stack.isEmpty()){stack.pop();num += 2;}}System.out.println(num);}}
}/**************************************************************Problem: 1342User: wzqwsrfLanguage: JavaResult: AcceptedTime:940 msMemory:40184 kb
****************************************************************/

C++ AC

#include <stdio.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
const int maxn = 1000002;
char input[maxn];
int main(){int n,i;while(scanf("%s",input) != EOF){n = strlen(input);stack<int> symStack;int maxLen = 0;for(i = 0 ; i < n; i++){if(input[i] == '('){symStack.push(i);}else if(input[i] == ')'  && !symStack.empty()){symStack.top();symStack.pop();maxLen += 2;}}printf("%d\n",maxLen);}return 0;
} 
/**************************************************************Problem: 1342User: wangzhenqingLanguage: C++Result: AcceptedTime:40 msMemory:2028 kb
****************************************************************/

这篇关于【九度】题目1342:寻找最长合法括号序列II(25分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1105562

相关文章

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

《五大特性引领创新!深度操作系统deepin25Preview预览版发布》今日,深度操作系统正式推出deepin25Preview版本,该版本集成了五大核心特性:磐石系统、全新DDE、Tr... 深度操作系统今日发布了 deepin 25 Preview,新版本囊括五大特性:磐石系统、全新 DDE、Tree

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close