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 次浏览

开始你的 职业生涯

完成课程获得认证

开始
广告