JavaScript-Algorithms
JavaScript-Algorithms copied to clipboard
Published
20 hours ago •
sisterAn
sisterAn
leetcode1047：删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S ，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
-
<= S.length <= 20000 -
S仅由小写英文字母组成。
附leetcode地址：leetcode
使用栈，进栈之前跟栈顶比较，如果不同则进栈，如果相同则栈顶元素出栈
var removeDuplicates = function(S) {
let stack = [S[0]]
for (let i = 1; i < S.length; i++) {
if (S[i] === stack[stack.length - 1]) {
stack.pop()
} else {
stack.push(S[i])
}
}
return stack.join('')
};
时间复杂度 O(n) 空间复杂度 O(n)
var removeDuplicates = function(S) {
let _ = [];
for(let i of S){
if(_.length && _[_.length - 1] == i){
_.splice(_.length - 1, 1)
}else{
_.push(i)
}
}
return _.join('')
};
解题思路： 新建Stack ； 遍历字符串S => S[i]； if Stack.top() === S[i] => Stack.pop else => Stack.push(S[i])
function Duplicates(S){
let Stack = []
let L = 0
let SL = S.length
for(let i = 0; i< SL;i++){
if(S[i] === Stack[L-1] ){
Stack.pop()
--L
}else{
Stack.push(S[i])
++L
}
}
return Stack.join('')
}
}
时间复杂度 O(n),空间复杂度 O(n)
@fanefanes 提个小建议: 变量
L可以去掉的, 因为L === Stack.length
遍历的时候尽量赋值常量， 要不然for每次循环会进行一次数组遍历查询 获取length
@fanefanes 提个小建议: 变量
L可以去掉的, 因为L === Stack.length遍历的时候尽量赋值常量， 要不然for每次循环会进行一次数组遍历查询 获取length
获取数组的 length 应该不需要遍历数组才能获得吧, 这是它的一个属性, O(1)的时间复杂度
var removeDuplicates = function(S) {
let stack = []
for(let v of S){
let peek = stack[stack.length-1]
if( peek === v){
stack.pop()
}else{
stack.push(v)
}
}
return stack.join('')
};
解法：利用栈
解题思路： 遍历字符串，依次入栈，入栈时判断与栈头元素是否一致，如果一致，即这两个元素相同相邻，则需要将栈头元素出栈，并且当前元素也无需入栈
解题步骤： 遍历字符串，取出栈头字符，判断当前字符与栈头字符是否一致
- 不一致，栈头字符进栈，当前字符进栈
- 一致，即栈头字符与当前字符相同相邻，都不需要进栈，直接进入下次遍历即可
遍历完成后，返回栈中字符串
代码实现：
const removeDuplicates = function(S) {
let stack = []
for(c of S) {
let prev = stack.pop()
if(prev !== c) {
stack.push(prev)
stack.push(c)
}
}
return stack.join('')
};
时间复杂度：O(n)
空间复杂度：O(n)
const removeDuplicates = (str) => {
if (str.length === 0) return ''
let newStr = str.slice(0)
for(let i = 0; i < newStr.length; i++) {
if(newStr[i] === newStr[i + 1]) {
newStr = newStr.replace(/(\w)\1/g, '')
i === 0 ? (i = i - 1) : (i = i - 2)
}
}
return newStr
}
递归加遍历
var removeDuplicates = function(S) {
if (S.length <= 1) {
return S
}
let left = 0
let right = left + 1
while (right < S.length) {
if (S.charAt(left) === S.charAt(right)) {
return removeDuplicates(S.slice(0, left) + S.slice(right + 1))
} else {
left += 1
right = left + 1
}
}
return S
};
利用栈
var removeDuplicates = function(S) {
let charStack = []
for (let s of S) {
const top = charStack[ charStack.length - 1 ]
// 相等则把栈顶元素删除，并且当前元素不入栈
if (s === top) {
charStack.pop()
} else {
charStack.push(s)
}
}
return charStack.join('')
};
递归 + 正则
var removeDuplicates = function(S) {
const repeatLenStrRe = /(.)\1/g
const replaceStr = S.replace(repeatLenStrRe, '')
if (replaceStr === S) {
return replaceStr
} else {
return removeDuplicates(replaceStr)
}
};
function removeDuplicates(S) {
let stack = []
for (let i = 0; i<S.length; i++){
if (stack.length) {
if(stack[stack.length - 1] == S[i]) {
stack.pop()
} else {
stack.push(S[i])
}
} else{
stack.push(S[i])
}
}
return stack.join('')
}
var removeDuplicates = function(S) {
// 第一种方法：使用栈
const stack = []
for (const w of S) {
const cur = stack.pop()
if (w !== cur) {
stack.push(cur)
stack.push(w)
}
}
return stack.join('')
// 第二种方法，字符串本身处理
for (let i = 0; i < S.length;) {
if (S[i] === S[i + 1]) {
S = S.slice(0, i) + S.slice(i+2)
i = 0
} else {
i++
}
}
return S
};
比较简单的题，用栈处理
var removeDuplicates = function(S) {
let res = [];
for (c of S) {
if (res.length > 0 && res[res.length-1] == c) {
res.pop();
} else {
res.push(c);
}
}
return res.join('');
};
var removeDuplicates = function(S) {
let len = S.length;
if(len === 0) return '';
let stack = [S[0]];
for(let i = 1; i < len; i++) {
if(stack[stack.length - 1] === S[i]) {
stack.pop();
} else {
stack.push(S[i]);
}
}
return stack.join('');
};
利用栈
var removeDuplicates = function(S) {
let len = S.length
let stack = []
for(let v of S){
let aLen = stack.length
if(stack[aLen - 1] === v){
stack.pop()
}else{
stack.push(v)
}
}
return stack.join('')
};
利用栈 存储以扫描过的字符，每次读取字符的时候都会跟栈顶元素进行比较，如果相同就推出栈顶元素，否则字符入栈
const removeDuplicates = (source: string) => {
if (source.length <= 1) return source;
const stack: string[] = [];
for (let i = 0; i < source.length; i++) {
const char = source.charAt(i);
if (stack.length > 0 && char === stack[stack.length - 1]) {
stack.pop();
continue;
}
stack.push(char);
}
return stack.join('');
};
function removeDuplicates(srt) {
const reg = /(\w)\1+/g;
const srt2 = srt.replace(reg, "");
if (srt !== srt2) return removeDuplicates(srt2);
return srt2;
}
function deleteNearChar(str){
function deleteChar(str){
let k = 0
while(k<str.length-1){
if(str.charAt(k)===str.charAt(k+1)){
let c = str.charAt(k)
while(c === str.charAt(k)){
let list = str.split('')
list.splice(k,1)
str = list.join('')
}
}else{
k++
}
}
return str
}
function isNearRepeat(str){
let list = str.split('')
return list.some((it,idx)=>list[idx]===list[idx+1])
}
while(isNearRepeat(str)){
str = deleteChar(str)
}
return str
}
console.log(deleteNearChar('abbaca'))
