Trung tâm cá nhân
Bài viết phát hành
từ bỏ
Bài viết phổ biến của tác giả
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
27
4
题目地址: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Ví dụ 1:
Input: "())" Output: 1
Example 2:
Input: "(((" Output: 3
Example 3:
Input: "()" Output: 0
Example 4:
Input: "()))((" Output: 4
Note:
1、 S.length<=1000；
2、 Sonlyconsistsof'('and')'characters.；
求最少添加几个括号才能使得整个表达式是合法的括号表达式。
遇到括号匹配题一般想到用栈。这题也不例外。
同样是对字符串进行一次遍历，如果遍历到的位置是左括号，那么要进行判断：
1、 如果栈顶是右括号，那么说明判断前面字符串缺少了几个括号；
2、 否则，需要直接进栈；
如果遍历到的位置是右括号，那么直接进栈。
我花了半个小时才把这个题做出来啊，错误的地方就在于左括号的判断上。第一，判断前面缺少几个括号的时候，我把栈所有的元素全部退栈了，这样就错误了，因为可能前面部分匹配，再往前的左括号需要等待后面的右括号来了之后才能判断。所以，这个问题的解决方法是如果cnt == 0，就不再退栈了。第二，我把stack.append('(')写错位置了，事实上，只要出现新的左括号，这个左括号一定进栈。由于我太愚蠢了，把进栈这步放在了对栈的判断里面，这样就导致了不符合栈的判断条件的地方就没把左括号放进去。。这个是不应该犯的错误。
时间复杂度是O(N)，空间复杂度是O(N)。
class Solution(object): def minAddToMakeValid(self, S): """ :type S: str :rtype: int """ if not S: return 0 stack = [] res = 0 for i, s in enumerate(S): if '(' == s: if stack and (stack[-1] == ')'): cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 if cnt == 0: break res += abs(cnt) stack.append('(') else: stack.append(')') cnt = 0 while stack: if stack.pop() == ')': cnt -= 1 else: cnt += 1 res += abs(cnt) return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
二刷使用了更简单的方法，直接把左括号进栈，遇到右括号时，如果栈里有左括号就弹出，否则需要加上右括号的个数。最后还要加上栈里面左括号的个数。
class Solution(object): def minAddToMakeValid(self, S): """ :type S: str :rtype: int """ res = 0 stack = [] for c in S: if c == '(': stack.append('(') else: if stack: stack.pop() else: res += 1 return res + len(stack)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
C++代码还是长一点。
class Solution { public: int minAddToMakeValid(string S) { stack s; int res = 0; for (auto c : S) { if (c == '(') { s.push('('); } else { if (!s.empty()) { s.pop(); } else { res ++; } } } return res + s.size(); } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
27
4
0
在 bash 中，() 和 $() 都创建了一个子 shell。 它们之间有什么区别？它们的典型用法是什么？ 最佳答案 () 只是创建一个复合命令，运行括号内的命令。 $() 做同样的事情，但也替换了
我有一个关于如何正确解析如下字符串的问题， "(test.function, arr(3,12), "combine,into one")" 进入以下列表， ['test.function', 'ar
假设我有一个非常大的文件，我想检查括号是否平衡。我不能使用堆栈，对吧？因为它会导致堆栈溢出。我可以使用什么方法？ 最佳答案 一个简单的计数器。由于您所做的只是计算括号: balance = 0 for
我希望这个线程成为覆盖和调用 toString 的优点/缺点的某种总结。有或没有空括号，因为这件事有时仍然让我感到困惑，即使我已经进入 Scala 很长一段时间了。 那么哪一个比另一个更可取呢？来自
本文关键词：有效，括号，括号匹配，栈，题解，leetcode, 力扣，Python, C++, Java 题目地址：https://leetcode.com/problems/valid-paren
本文关键词：括号, 括号生成，题解，leetcode, 力扣，Python, C++, Java 题目地址：https://leetcode.com/problems/generate-parent
我遇到了几天的问题。 我在编译我的程序时收到此警告。 In member function 'void CClientManager::RESULT_SAFEBOX_LOAD(CPeer*, SQLM
题目地址：https://leetcode.com/problems/best-sightseeing-pair/ 题目描述 Given an array A of positive intege
我想匹配以 ')' 结尾的字符串。我使用模式: "[)]\b" or ".*[)]\b" 它应该匹配字符串: x=main2.addMenu('Edit') 但它不起作用。怎么了？ 最佳答案 \b
我正在尝试使用 paredit 在 Light Table 上编辑 Clojure/ClojureScript 文件，但该插件似乎不起作用。当我打开一个括号时，它没有关闭。 但是，插件已安装，如插件列
我在 R 中使用正则表达式。我试图找出字符向量中某些字符串末尾带括号的内容。我能够在括号内的内容存在时找到它，但我无法在没有括号的输入中排除非括号内的内容。 例子: > x gsub("(.*?)(
我需要一个正则表达式，其中允许以任何顺序使用空格、括号和连字符的任何数字。但是有必须最后是“+”(加号)。 最佳答案 您可以使用正则表达式: ^[\d() -]+\+$ 解释: ^ : Start
这个问题在这里已经有了答案: 关闭 10 年前。 Possible Duplicate: What is the purpose of a self executing function in ja
在 Common Lisp 中，特殊运算符 quote 使得后面跟着未计算的任何内容，例如 (quote a) -> a (quote {}) -> {} 但为什么表单 (quote ()) 给我 n
我有一个程序需要在用户输入括号时进行处理。我尝试过: root.bind("") 但是没用，和一样 root.bind("") 如何将括号事件绑定(bind)到 Tkinter 中？请帮助我 最佳答案
当我看到名称中带有括号的函数时，我正在阅读源代码: extern int LIB_(strcmp) ( const char* s1, const char* s2 ); extern char LI
是否可以改变 Hello, this is Mike (example) 到 Hello, this is Mike 将 JavaScript 与正则表达式一起使用？ 最佳答案 "Hello, thi
题目地址：https://leetcode.com/problems/different-ways-to-add-parentheses/description/ 题目描述 Given a str
我在 react 原生项目的 VSCode 中使用 prettier，它删除了混合运算符中的括号或使用括号声明 var 时。如何防止 prettier 这样做 示例 1: const foo = (
我有一个包含一些引文的 R Markdown 文档。我正在使用默认的引文样式，这通常对我很有效。但是我有一些句子位于括号内，在这些句子中，我想在不添加第二组括号的情况下引用作品。也就是说，我想取消引用
Tôi là một lập trình viên xuất sắc, rất giỏi!