leetcode1209：删除字符串中的所有相邻重复项 II
sisterAn opened this issue · 11 comments
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：
输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。示例 2：
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"示例 3：
输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"提示：
1 <= s.length <= 10^52 <= k <= 10^4s中只含有小写英文字母。
附赠 leetcode 地址：leetcode
var removeDuplicates = function(s, k) {
let stack = [];
for(let _s of s){
const last = stack.pop();
if(!last || last[0] !== _s){
stack.push(last)
stack.push(_s)
}else if(last.length < k-1){
stack.push(last + _s)
}
}
return stack.join('')
};function delStr(s = '', k = 2) {
if (typeof s !== 'string' || k < 2) {
return;
}
let c = new RegExp(`(.)\\1{${k-1}}`, 'g');
while (s !== s.replace(c, '')) {
s = s.replace(c, '');
}
return s;
}原理跟昨天的题是一样的，不过昨天的题是一次入栈一个，今天是k个。那我们就让它每次入栈 k-1 个，站头的 k-1 个元素的第一个如果与当前准备入栈的元素相同，则代表k个元素是一样的，则无需入栈。
var removeDuplicates = function(s, k) {
let stack = [];
for(let c of s){
const prev = stack.pop();
if(!prev || prev[0] !== c){
stack.push(prev)
stack.push(c)
}else if(prev.length < k-1){
stack.push(prev + c)
}
}
return stack.join('')
};解答：利用栈
解题**： 遍历字符串依次入栈，入栈时，判断当前元素与栈头元素是否一致，如果不一致则入栈，如果一致，判断栈头字符是否长度为 k - 1 ，如果为 k-1 ，即加入该字符时，满足连续相同字符 k 个，此时，需要栈头出栈，当前字符不进栈，如果小于 k-1 ，则取出栈头字符，加上当前字符，重新入栈
代码实现：
const removeDuplicates = function(s, k) {
let stack = []
for(let c of s) {
let prev = stack.pop()
if(!prev || prev[0] !== c) {
stack.push(prev)
stack.push(c)
} else if(prev.length < k-1) {
stack.push(prev+c)
}
}
return stack.join('')
};时间复杂度：O(n)
空间复杂度：O(n)
暴力来一波
var removeDuplicates = function(s, k) {
function findRepeatPos (s, k) {
for (let i = 0; i < s.length - k + 1; i++) {
let flag = true
for (let j = i; j < i + k - 1; j++) {
if (s[j] !== s[j + 1]) {
flag = false
break
}
}
if (flag === true) {
return [i, i + k - 1]
}
}
return [-1]
}
while (true) {
let [start, end] = findRepeatPos(s, k)
console.log(start, end)
if (start === -1) {
return s
} else {
s = s.slice(0, start) + s.slice(end + 1)
}
}
return s
};function delStr(s = '', k = 2) { if (typeof s !== 'string' || k < 2) { return; } let c = new RegExp(`(.)\\1{${k-1}}`, 'g'); while (s !== s.replace(c, '')) { s = s.replace(c, ''); } return s; }
这种做法可以，但是它采用循环匹配替换，花费时间较长，需要考虑一下时间复杂度问题
var arr = 'pbbcggttciiippooaais'.split(''), k = 2;
var startIndex = 0;
while(startIndex < arr.length) {
var num = 1;
while(arr[startIndex + num] === arr[startIndex] && num < k) {
num++;
}
if (num === k) {
arr.splice(startIndex, num);
startIndex = Math.max(0, startIndex - k + 1);
} else {
startIndex++;
}
}
采用两个栈来进行:
function removeDuplicateK(s, k) {
if(k <= 0) {
return s;
}
let stack1 = new Stack();
for(let i=0; i<s.length; i++) {
let iValue = s[i]
stack2 = new Stack(),
j = 0,
isValid = true;
while(j < k-1) {
let popValue = stack1.pop();
if(popValue !== null){
stack2.push(popValue);
}
if(popValue === null || popValue !== iValue) {
isValid = false;
break;
}
j += 1;
}
if(!isValid) {
while(stack2.length > 0) {
stack1.push(stack2.pop());
}
stack1.push(iValue);
}
}
return stack1.dataStore.join('');
}正则 + 递归
var removeDuplicates = function(s, k) {
if (s.length < k) {
return s
}
const repeatLenStrRe = new RegExp(`(.)\\1{${ k - 1 }}`, 'g')
const replaceStr = s.replace(repeatLenStrRe, '')
// 说明没有需要再匹配的了
if (replaceStr === s) {
return replaceStr
} else {
return removeDuplicates(replaceStr, k)
}
};大家来评评理。对于以下测试用例，我输出“is”有什么不对吗
"pbbcggttciiippooaais"
2预期结果
"ps"
下面是我的代码
var removeDuplicates = function(s, k) {
for (let left = 0; i < s.length - k + 1; left++) {
let right = i;
while (s[right + 1] == s[left]) {
right = right + 1;
}
const gap = right - left + 1;
if (gap >= k) {
s = s.substr(0, i) + s.substr(i + gap, s.length)
left = -1
}
}
return s
};执行过程输出
pbbcggttciiippooaais --> pcggttciiippooaais
pcggttciiippooaais --> pcttciiippooaais
pcttciiippooaais --> pcciiippooaais
pcciiippooaais --> piiippooaais
piiippooaais --> pppooaais
pppooaais --> ooaais
ooaais --> aais
aais --> is
和删除相邻重复项是同一个类型，利用栈来存储扫描过的字符，不一样的是该题支持 k 个，这个理论上可以按照上一题一样的原则，直接推栈就好了，但是出栈的时候，考虑到 假如 k 值很大，会做很多重复性的 pop 工作，所以我这里 将 栈的节点从单纯存储读取的字符， 改为 一个 对象，对象保存了读取的字符，和已经读取的字符数量，这样每次 pop 只需要一次即可完成任务
interface StackNode {
value: string;
count: number;
}
const removeDuplicates = (source: string, k: number) => {
if (source.length <= 0 || k <= 0 || source.length < k) return source;
const stack: StackNode[] = [];
for (let i = 0; i < source.length; i++) {
const char = source[i];
if (stack.length <= 0) {
stack.push({ value: char, count: 1 });
continue;
}
const lastStackNode = stack[stack.length - 1];
if (lastStackNode.value !== source[i]) {
stack.push({ value: char, count: 1 });
continue;
}
if (lastStackNode.count === (k - 1)) {
stack.pop();
} else {
lastStackNode.count++;
}
}
return stack.reduce((prev, cur) => prev + cur.value.repeat(cur.count), '');
};