数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中移除字符串中所有相邻重复字符 II
假设给定一个字符串 s，k 次重复移除包括从字符串 s 中选择 k 个相邻且相等的字母并将其移除，导致已删除子字符串的左侧和右侧连接在一起。我们将对给定的字符串 s 重复进行 k 次重复移除，直到我们无法进行任何更改。我们必须找到所有此类重复移除后最终的字符串。因此，如果输入类似于 s = “deeedbbcccbdaa”，k = 3，则输出将是 “aa”，首先删除 “eee” 和 “ccc”，我们将得到 “ddbbbaa”，然后删除 “bbb”，字符串将是 “dddaa”，然后删除 “ddd”，输出将是 “aa”
为了解决这个问题，我们将遵循以下步骤：
- ans := 空字符串
- 创建一个字符-整数对的栈，n := 字符串的大小
- 对于 i 从 0 到 n
- x := s[i]
- 如果栈不为空且栈顶元素的整数部分 = k，则从栈中删除顶元素
- 如果 i = n，则中断
- 如果栈为空或栈顶的字符不是 x，则将对 (x, 1) 插入到栈中，并将 i 增加 1
- 否则增加栈顶元素的整数部分，并将 i 增加 1
- 当栈不为空时
- temp := 栈顶元素
- 当 temp 的整数部分不为 0 时
- ans := ans + temp 的字符部分
- 将 temp 的整数部分减少 1
- 从栈中删除顶元素
- 反转 ans 字符串并返回。
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans = "";
stack < pair<char, int> > st;
int n = s.size();
for(int i = 0; i <= n;){
char x = s[i];
if(!st.empty() && st.top().second == k)st.pop();
if(i == n)break;
if(st.empty() || st.top().first != x){
st.push({x, 1});
i++;
} else {
st.top().second++;
i++;
}
}
while(!st.empty()){
pair <char, int> temp = st.top();
while(temp.second--) ans += temp.first;
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
}输入
"deeedbbcccbdaa" 3
输出
aa
更新于：2020年4月30日
620 次浏览
广告