coding everyday

编程面试题 https://interview.codeplex.com

C++博客 首页 新随笔 联系 聚合 管理
  12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks
这个问题很简单,大学学数据结构的时候,讲堆栈一章的时候作为其中一个例子来说的。但是如果面试中被问到这个题,我想用堆栈来做应该不能被接受吧,理由是空间和时间的代价都挺高的。

有没有稍微好点的算法呢?介绍个时间O(n), 空间O(1)的算法。

既然我们只是要找出括号有没有匹配就行了,那我们用一种方式记下左括号和右括号的次数不就可以了,例如left_count, right_count。它们的差为0不就好了?只要不为0,肯定就不匹配了,对吧?更进一步,为啥非要用2个变量呢,一个就够了嘛。遇到左括号++,遇到右括号--,最后为0即匹配。
 1 bool is_brackets_match(char *const input) {
 2     if (input != nullptr) {
 3         char *p = input;
 4         int count = 0;
 5 
 6         while (*p != '\0') {
 7             if (*p == '(')
 8                 ++count;
 9             else if (*p == ')')
10                 --count;
11 
12             p++;
13         }
14 
15         if (count == 0)
16             return true;
17     }
18     return false;
19 }
posted on 2013-07-13 17:20 everyday 阅读(765) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

Feedback

# re: 括号匹配问题 2013-12-12 06:40 san
不行吧?如果是)()()()(
这样(和)数量相同,可是也不能算是匹配啊?  回复  更多评论
  


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