数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查是否可以通过最多将括号移动到任一端 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。否则，将')'的值增加 1。
如果 open 和 closed 不相等，则返回 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'变量，并初始化为零。
开始遍历字符串
如果当前字符是'('，则将 count 的值增加 1。否则，将 count 的值减少 1。
如果'count'的值小于零，则将'res'的值增加 1，并将 count 更新为零。
循环迭代完成后，返回'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)，因为我们没有使用动态空间。
96 次浏览
