检查是否可以通过将括号向两端移动最多 K 次来获得平衡括号
在这个问题中，我们需要检查是否可以通过将字符串的末尾最多移动 K 个字符来获得括号的有效平衡子序列。
为了解决这个问题，我们可以使用堆栈数据结构。解决问题的逻辑是，如果我们在'('(开括号)之前找到超过 K 个')'(闭括号)，我们就不能将字符串变成有效的子序列。
问题陈述– 我们给出了包含'('和')'括号序列的字符串 str。字符串的长度为 N。此外，我们给出了一个正整数 K。我们需要检查是否可以通过在字符串末尾移动字符串的最多 K 个字符来将给定的字符串变成有效的括号子序列。根据我们是否可以生成有效的子序列打印'是'或'否'。
示例
输入– str = ")()()(", k = 1
输出– '是'
解释– 在将第一个字符移动到末尾后字符串末尾，我们可以得到'()()()'，这是一个有效的括号子序列
输入– str = "))())()(((", k = 2
输出– 否，
解释– 我们最多可以在字符串末尾移动 2 个字符。因此，在移动字符串末尾的前 2 个字符后，我们可以得到'())()((())'，这不是有效的括号子序列。
输入– str = '()(', k = 10
输出– 否
解释– 字符串不包含相同数量的开括号和闭括号，因此无法创建有效的括号子序列。
方法1
我们将使用堆栈数据结构来按此方法解决问题。
算法
如果 n 为奇数，则返回 false，因为如果字符串长度为奇数，则我们无法获得匹配括号的子序列。
定义"open"和"close"变量并用零初始化。
使用循环遍历字符串。如果当前字符是'('，则将 open 的值增加 1。否则，将')'的值增加 1。
如果 open 和 closed 不相等，则返回 false，因为如果左括号和右括号的总数不相等，我们就无法获得平衡子序列。
用零初始化'res'变量并定义一个空堆栈。
再次开始遍历字符串。
如果当前字符是'('，则将其推送到堆栈。
如果当前字符是')'，并且堆栈不为空，则从堆栈中删除顶部元素。否则，将'res'的值增加 1，因为我们需要移动末尾的字符。
最后，检查'res'的值是否小于 K。如果是，则返回 true。否则，返回 false。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数检查是否可以根据给定条件使字符串平衡
bool getMinMoves(string s, int n, int k) {
// 如果字符串的长度为奇数，则无法使字符串平衡
if(n % 2 != 0) {
return false;
}
// 计算左括号和右括号的总数
int open = 0, close = 0;
// 遍历字符串
for (int i = 0; i < n; i++) {
// 如果当前字符是左括号，则增加 open。否则增加 close
if (s[i] == '(') {
open++;
} else {
close++;
}
}
// 如果左括号的数量不等于右括号的数量，则无法使字符串平衡
if (open != close) {
return false;
}
// 存储使字符串平衡所需的移动
int res = 0;
// 定义堆栈
stack<char> st;
// 遍历字符串
for (int i = 0; i < n; ++i) {
// 如果当前字符是打开括号，则将其推送到堆栈
if (s[i] == '(') {
st.push(s[i]);
} else {
if(!st.empty()) {
st.pop();
} else {
// 增加res
++res;
}
}
}
// 如果 res 小于或等于 k，则返回 true。否则返回 false
if (res <= k) {
return true;
} else {
return false;
}
}
int main() {
string str = "))())()(((";
int K = 2;
if (getMinMoves(str, str.length(), K)) {
cout << "是的，通过将字符移动到任一端最多 K 次，可以生成有效的括号";
} else {
cout << "否，通过将字符移动到任一端最多 K 次，无法生成有效的括号";
}
return 0;
}
输出
否，通过将字符移动到任一端最多 K 次，无法生成有效的括号
时间复杂度 – 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(n % 2 != 0) {
return false;
}
int open = 0, close = 0;
// 计算左括号和右括号的数量
open = count(s.begin(), s.end(), '(');
close = count(s.begin(), s.end(), ')');
// 如果左括号的数量不等于右括号的数量，则无法使字符串平衡
if (open != close) {
return false;
}
// 存储使字符串平衡所需的移动次数
int res = 0;
int count = 0;
// 遍历字符串
for (int i = 0; i < n; ++i) {
// 如果当前字符是左括号，则计数加 1
if (s[i] == '(') {
++count;
} else {
// 将 count 减 1
--count;
// 如果 count 变为负数，则将 count 更新为 0，并将 res 增加 1。
if (count < 0) {
// 更新 count
count = 0;
// 增加 res
++res;
}
}
}
return (res <= k);
}
int main() {
string str = ")()()(";
int K = 1;
if (getMinMoves(str, str.length(), K)) {
cout << "是的，最多将字符移动到任一端 K 次即可生成有效的括号";
} else {
cout << "否，最多将字符移动到任一端 K 次即可生成有效的括号";
}
return 0;
}
输出
是的，最多将字符移动到任一端 K 次即可生成有效的括号
时间复杂度 – O(N)，因为我们遍历字符串。
空间复杂度 – O(1)，因为我们不使用动态空间。
