本文主要是介绍【九度】题目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分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!