C++ 检查是否可以通过最多K次移动括号到末尾来获得平衡的括号

在这个问题中，我们需要通过将字符串中最多移动K个字符到末尾，来检查是否可以得到有效的平衡的括号子序列。

为了解决这个问题，我们可以使用栈数据结构。解决问题的逻辑是，如果我们在遇到开括号“（”之前找到了超过K个关闭括号“）”，则无法将字符串转换为有效的子序列。

问题描述 - 我们给出一个包含括号序列“（”和“）”的字符串str。字符串的长度为N。同时，我们给出一个正整数K。我们需要检查是否可以通过将字符串中最多移动K个字符到字符串末尾，将给定字符串转换为有效的括号子序列。根据是否可以创建一个有效的子序列，打印“Yes”或“No”。

示例示例

输入 - str = “)()()(“, k = 1

输出 - ‘Yes’

解释 - 将第一个字符移动到字符串末尾后，我们可以得到“()()()”，这是一个有效的括号子序列。

输入 - str = “))())()(((“, k = 2

输出 - No

解释 - 我们最多可以将2个字符移动到字符串末尾。因此，在将前2个字符移动到字符串末尾之后，我们可以得到“())()((())”，这不是一个有效的括号子序列。

输入 - str = ‘()(‘, k = 10

输出 - No

解释 - 字符串中没有相同数量的开括号和闭括号，因此无法创建有效的括号子序列。

方法1

我们将使用栈数据结构来解决这个问题。

步骤

• 如果n是奇数，则返回false，因为如果字符串长度是奇数，我们无法获得一个平衡的括号子序列。

• 定义“open”和“close”变量，并初始化为零。

• 使用循环遍历字符串。如果当前字符是“（”，则将open的值增加1。否则，将close的值增加1。

• 如果open和close不相等，则返回false，因为如果开放和关闭的括号的总数不相等，我们无法获得一个平衡的子序列。

• 用零初始化“res”变量，并定义一个空栈。

• 重新遍历字符串。

• 如果当前字符是“（”，将其推入栈中。

• 如果当前字符是“）”，并且栈不为空，则从栈中移除顶部元素。否则，将“res”的值增加1，因为我们需要将字符移到末尾。

• 最后，检查“res”的值是否小于K。如果是，则返回true。否则，返回false。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if it is possible to make the string balanced according to the given condition
bool getMinMoves(string s, int n, int k) {
   // If the length of the string is odd, it is not possible to make the string balanced
   if(n % 2 != 0) {
      return false;
   }
   // count the total number of opening and closing brackets
   int open = 0, close = 0;
   // Traverse the string
   for (int i = 0; i < n; i++) {
      // If the current character is opening a bracket, increment open. Else increment close
      if (s[i] == '(') {
          open++;
      } else {
          close++;
      }
   }
   // If the number of opening brackets is not equal to the number of closing brackets, it is not possible to make string balanced
   if (open != close) {
      return false;
   }
   // to store moves required to make string balanced
   int res = 0;
   // Defining the stack
   stack<char> st;
   // Traverse the string
   for (int i = 0; i < n; ++i) {
      // If the current character is opening the bracket, push to the stack
      if (s[i] == '(') {
          st.push(s[i]);
      } else {
          if(!st.empty()) {
            st.pop();
            } else {
                // Increment the res
                ++res;
            }
       }
   }
   // If res is less than or equal to k, then return true. Else return false
   if (res <= k) {
      return true;
   } else {
      return false;
   }
}
int main() {
   string str = "))())()(((";
   int K = 2;
   if (getMinMoves(str, str.length(), K)) {
      cout << "Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times";
   } else {
      cout << "No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times";
   }
   return 0;
}

输出

No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times

时间复杂度 – O(N)，因为我们遍历了字符串。

空间复杂度 – O(N), 因为我们使用了栈。

方法2

在这个方法中，我们将写出优化的代码，不使用栈来改善代码的空间复杂度。

步骤

• 如果字符串的长度是奇数，则返回false。

• 使用count()方法计算‘(’和‘)’字符的总数。如果两者的计数不相等，则返回false。

• 定义’res’和’count’变量，并初始化为零。

• 开始遍历字符串。

• 如果当前字符是 ‘(‘, 将计数值加1。否则，将计数值减1。

• 如果’count’的值小于零，则将’res’的值加1，并将计数值更新为零。

• 循环迭代完成后，返回’res <= k’的值。

示例

#include <bits/stdc++.h>
using namespace std;
bool getMinMoves(string s, int n, int k) {
   // If the length of the string is odd, it is not possible to make the string balanced
   if(n % 2 != 0) {
      return false;
   }
   int open = 0, close = 0;
   // count the number of opening and closing brackets
   open = count(s.begin(), s.end(), '(');
   close = count(s.begin(), s.end(), ')');
   // If the number of opening brackets is not equal to the number of closing brackets, it is not possible to make string balanced
   if (open != close) {
      return false;
   }
   // to store moves required to make string balanced
   int res = 0;
   int count = 0;
   // Traverse the string
   for (int i = 0; i < n; ++i) {
      // If the current character is opening bracket, increment count by 1
      if (s[i] == '(') {
          ++count;
      } else {
          // Decrement count by 1
          --count;
          // If the count becomes negative, then update the count to 0 and increment res by 1.
          if (count < 0) {
              // Update the count
              count = 0;
              // Increment the res
              ++res;
          }
      }
   }
   return (res <= k);
}
int main() {
   string str = ")()()(";
   int K = 1;
   if (getMinMoves(str, str.length(), K)) {
      cout << "Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times";
   } else {
      cout << "No, It is not possible to make valid parenthesis by moving characters to either end at most K number of times";
   }
   return 0;
}

结果

Yes, It is possible to make valid parenthesis by moving characters to either end at most K number of times

时间复杂度 – O(N)，因为我们遍历字符串。

空间复杂度 – O(1)，因为我们不使用动态空间。