計算需要移除的配對數，以使所有平衡括號子序列為空

C 編譯器將字串視為字元數組，因此很容易根據位置刪除字串中的字元。必須檢查字串的第一個和最後一個位置是否存在括號，並且必須將其刪除。該字串可以複製到另一個變數中並顯示。

C 中有許多預定義函數可以有效地用來操作字串。在 C 語言中，借助函數可以輕鬆實現從起始位置或結束位置刪除字元。

從字串中刪除開始和結束括號

括號是單一字符，是輸入字串的一部分，可以按照下面給出的邏輯和演算法從字串中刪除

字元是我們在鍵盤上看到的任何字母數字鍵，它儲存在 C 中的字元變數中。

() 在 c 中稱為括號。我們需要在用戶輸入的字串中識別該字符，並將其從字串中刪除。

數組是一個變量，它具有許多由單一名稱和連續編號尋址的儲存位置，而字串是一個字元數組。

在許多情況下，我們需要從字串中刪除括號，例如在解決正規表示式時。

文法

函數 countRemoval 接受字串 str 作為輸入並傳回一個整數值，該值表示使字串中所有平衡括號子序列為空所需的刪除對的數量。此函數使用變數 count 來追蹤所需的刪除次數，最初設定為 0。它還使用變數 Balance 來追蹤字串中左括號和右括號的數量之間的平衡。然後該函數迭代字串的長度並檢查每個索引處的字元。如果該字元是左括號，則餘額加1，如果是右括號，則餘額減1。如果餘額變成負數，則說明多了一個右括號，移除次數為加 1，餘額重設為 0。循環後，計數更新為包含剩餘餘額除以 2，作為使字串中所有平衡括號子序列為空所需的刪除量。

int countRemoval(string str) {
   int count = 0;
   int balance = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '(') {
         balance++;
      } else {
         balance--;
      }
      if (balance < 0) {
         count++;
         balance = 0;
      }
   }
   count += balance / 2;
   return count;
} 

演算法

• 第 1 步 - 宣告 str1、str2，初始化為 null。

• 第 2 步 - 宣告整數變數 len,n,i

• #第 3 步 - 從控制台接受 str1

• 第 4 步 - 檢查第一個字元是否為 (

• #步驟 5 - 如果是 n = 1

• 第 6 步 - 當 n<輸入字串 len 的長度時，將 str1 中的每個字元複製到 str2 <输入字符串 len 的长度时，将 str1 中的每个字符复制到 str2

• 第 7 步 - 檢查 str2 的最後一個字元是否為 )。

• 第 8 步 - 如果是，請將其替換為 \0。

• 第 9 步 - 列印 str2，其中包含輸入字串減號 ()。

方法

方法 1 - 暴力遞歸：在第一種方法中，我們使用暴力遞歸來尋找所有可能的子序列並檢查它們是否平衡。如果子序列是平衡的，我們刪除一對括號併計算刪除的括號對的數量。我們計算清空字串所需的最少對刪除次數。

方法 2 - 動態程式設計：第二種方法使用動態程式來最佳化解決方案。我們可以使用 2D DP 表來儲存從索引「i」到「j」的子字串所需的最小刪除次數。我們迭代字串並根據給定條件填充 DP 表。

方法 1 暴力遞迴

程式碼

在這段程式碼中，我們檢查所有可能的子序列組合，這導致了指數時間複雜度。對於較大的輸入，此方法可能效率不高。

#include <iostream>
#include <string>
using namespace std;

int countRemovalsRecursion(const string &s, int index, int open) {
   if (index == s.size()) {
      return open;
   }

   if (s[index] == '(') {
      return countRemovalsRecursion(s, index + 1, open + 1);
   } else if (open > 0) {
      return countRemovalsRecursion(s, index + 1, open - 1);
   } else {
      return 1 + countRemovalsRecursion(s, index + 1, open);
   }
}

int main() {
   string s = "(()())(";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Brute Force Recursion): " << countRemovalsRecursion(s, 0, 0) << endl;
   return 0;
}

輸出

Input string: (()())(
Minimum removals (Brute Force Recursion): 1

方法2

範例

此動態規劃解決方案計算清空所有平衡括號子序列所需的最小刪除次數。它迭代字串，用左括號的數量更新一維 DP 表，並傳回最終 DP 值作為最小移除量。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countRemovalsDP(const string &s) {
   int n = s.size();
   vector<int> dp(n + 1, 0);

   for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
         dp[i + 1] = dp[i] + 1;
      } else {
         dp[i + 1] = max(dp[i] - 1, 0);
      }
   }
   return dp[n];
}

int main() {
   string s = "(()())()";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Dynamic Programming): " << countRemovalsDP(s) << endl;
   return 0;
}

輸出

Input string: (()())()
Minimum removals (Dynamic Programming): 0

結論

C語言的基本概念，如字元和字串資料類型有什麼區別，字串分隔符，如何初始化字串和數組，數組第一個字元為索引0的位置的計算並且該程式中使用最後一個字元必須為空才能獲得正確的輸出。

程式中括號的刪除是透過實作 C 程式設計的基本、簡單概念來實現的。

以上是計算需要移除的配對數，以使所有平衡括號子序列為空的詳細內容。更多資訊請關注PHP中文網其他相關文章！