84、【栈与队列】leetcode ——1047. 删除字符串中的所有相邻重复项:栈+双指针解法(C++版本)
题目描述
原题链接:1047. 删除字符串中的所有相邻重复项
解题思路
一、栈顶匹配重复元素
本题需要删除重复且相邻元素,存入不重复元素。根据相邻特点
,可采用栈进行实现。
当栈顶元素和遍历的字符串中的字符相同时,则将其弹栈。然后遍历下一个元素,直至全部遍历完,让各个相邻元素都不重复的存入栈中。再将其弹栈存入到子串中,因为栈为后进先出,因此需要让字符串进行逆置,恢复原始顺序。
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
string res = "";
for(char ch : s) {
// 当栈为空或者栈顶元素与ch不相同,则将ch压入栈中
if(st.empty() || st.top() != ch) {
st.push(ch);
} else {
// 如果栈中不为空而且栈顶元素与ch相等,则弹出已存入的栈顶元素
st.pop();
}
}
// 存入res中
while(!st.empty()) {
res += st.top();
st.pop();
}
// 因为从栈中弹出的元素为逆序,因此需要将字符串再逆序,让顺序正过来
reverse(res.begin(), res.end());
return res;
}
};
时间复杂度
O
(
n
)
O(n)
O(n)
空间复杂度
O
(
n
)
O(n)
O(n)
二、双指针方法1:先判定,再填充
初步想法是类似于 移除链表元素 的方式,采用快慢双指针存储符合条件的元素,不存储不符合条件的元素。
此题和移除链表元素题的区别,在于本题需要对比的不仅仅是原始链表中的相邻元素,还需要再与已经存入的元素进行对比。
整体思路是在填充前,先对比当前待填充元素与未来填充元素的情况,再对比当前待填充元素与上一个已填充元素的情况,都不重复时,则填充该元素。
设置j
指针用来存储符合条件的元素,始终指向待存储位置的下标。
设置i
指针遍历原字符串,每次首先对比s[i]
与s[i+1]
字符是否相同,如果相同,则不填充,需要跳过这两个字符。如果不相同,再对比s[i]
与s[j - 1]
中字符是否相同,如果相同,则让j--
,让下一次存储覆盖该存入元素。
当原始字符串中相邻元素不相同,而且待存入元素与新字符串的末尾元素不相同时,存入该元素。
其实,就相当于是i为pre指针,i+1为cur指针,j为temp指针(用于存入新元素,指向新子串末尾的下一个位置)。每次对比pre指针和cur指针指向元素,然后再对比pre指针和(temp-1)指针对比。
class Solution {
public:
string removeDuplicates(string s) {
int n = s.size();
// 用j指向新的待存储元素的位置
int j = 0;
for(int i = 0; i < n; i++) {
// 当s[i]与s[i+1]相同时,跳过这两个元素
if(i + 1 < n && s[i] == s[i + 1])
i++; // 先加1,之后循环结尾还会再加1,从而实现跳过这两个重复元素
// 当s[i]与s[j - 1]中元素相同时,让此位置元素可被替换,执行j--,并再执行i++跳过该元素
else if(j > 0 && s[j - 1] == s[i])
j--;
// 当相邻元素不重复而且已存入元素和新存入元素不重复时,加入该元素
else
s[j++] = s[i];
}
s.resize(j);
return s;
}
};
时间复杂度
O
(
n
)
O(n)
O(n)
空间复杂度
O
(
1
)
O(1)
O(1)
三、双指针方法2:先填充,再判定回退
方法1中,思路是填充前先查看未来情况和原先已填充情况。方法2是先填,再判定,不满足条件,则回退到未填充的时候。
因为本题需要与之前已填充过的元素进行对比,如果先对比后填充,不仅需要对比未来情况,还需要对比已有情况。该方式可以提前跳过不满足条件的情况。
方法2采用先填充后对比的策略,从而让对比方式变成只需对比当前与之前的填充情况即可,但会需要将不满足的条件进行退回,相比于方法1会多填充一次。
采取策略是设置一个i
指针用于遍历整个字符串,另设置一个j
指针进行填充。每次先进行填充,填充完后,与已填充过的上一个元素进行对比,如果相同,则放弃此次填充,回退到之前的位置。如果不相同,则填充此次位置。
class Solution {
public:
string removeDuplicates(string s) {
int n = s.size();
int j = 0;
for(int i = 0; i < n; i++) {
s[j] = s[i]; // 先填充
if(j > 0 && s[j] == s[j - 1]) // 填充后与上一个填充元素对比
j--; // 当发现与之前元素相同,则回退
else
j++; // 与之前元素不同,则填充并指向下一个待填充位置
}
s.resize(j);
return s;
}
};
时间复杂度
O
(
n
)
O(n)
O(n)
空间复杂度
O
(
1
)
O(1)
O(1)
参考文章:1047. 删除字符串中的所有相邻重复项
相关文章
- 吐槽C++:C++ 类成员变量初始化 之 初始化带有参数的构造函数 的类成员变量。
- paip.提升用户体验----gcc c++ JIT-debugging 技术
- VS中c++文件调用c 函数 ,fatal error C1853 预编译头文件来自编译器的早期版本号,或者预编译头为 C++ 而在 C 中使用它(或相反)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- LeetCode 罗马数字转整数(执行用时: 16 ms , 在所有 C++ 提交中击败了 49.87% 的用户)
- 关于C++ const 的全面总结
- VC++ XP/WIN7系统中删除残留托盘图标的方法(附源码)
- C++ GDI资源泄漏导致的程序异常的解析
- C++装饰器模式
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 由先序和中序序列构建一棵二叉树【C++版】
- PAT 1141 C++ 版
- 【C++要笑着学】内联函数 inline | auto关键字(C++11) | 范围for | 关键字 nullptr