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

Arnab Chakraborty

更新於：2020 年 9 月 2 日

237 次瀏覽

開始你的 職業生涯

完成課程獲得認證

開始