posts - 33,  comments - 25,  trackbacks - 0

本题有非常直接的解法,根据输入先将括号字符串还原,再对还原后的括号字符串进行计算,但效率不高,需要n2+n的时间复杂度,其实可以用线性扫描在O(n)的时间内解决,具体思路如下:
在扫描的时候,利用一个栈保存已有的左括号信息(包括剩下几个未匹配的左括号与已经匹配左括号的个数),在扫描到输入j的时候,有以下三种情况(设i为j前一个输入):
1. i == j - 1;这种情况非常简单,表明新输入的右括号与自身所带的左括号匹配,直接输出1,更新栈顶元素信息.
2. i < j - 1; 这种输入表明j位置上的右括号自带了比自身所需更多的左括号,将剩余的左括号相关信息入栈保存.
3. i == j;表明位置j并没有任何自身的左括号,需要向栈中借,并更新栈相关信息.

Code

 

posted on 2009-03-24 20:29 肖羽思 阅读(646) 评论(0)  编辑 收藏 引用 所属分类: ZOJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜