数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最小括号添加
假设我们有一个只包含 '(' 和 ')' 的字符串 s，我们需要找到可以插入以使字符串平衡的最小括号数。
因此，如果输入像 "(()))("，则输出将为 2 作为 "(()))("，这可以通过像 "((()))()" 这样的方式保持平衡。
要解决此问题，我们将遵循以下步骤 −
:= 0, cnt := 0
for 初始化 i := 0，当 i < s 的大小，更新（增加 i 1），执行 −
如果 s[i] 等于 '(', 则 −
（增加 o 1）
否则
如果 o 非零，则 −
（减少 o 1）
否则
（增加 cnt 1）
返回 cnt + o
让我们看看以下实施，以获得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s) {
int o = 0;
int cnt = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '('){
o++;
} else {
if(o)
o--;
else
cnt++;
}
}
return cnt + o;
}
};
int main(){
Solution ob;
cout << (ob.solve("(()))("));
}输入
Input:
"(()))("输出
2
更新于：2020 年 9 月 2 日
237 次浏览
广告