带你读《图解算法小抄》十七、栈(5)https://developer.aliyun.com/article/1348075?groupCode=tech_library
6.删除字符串中的所有相邻重复项
给定一个由大小写字母组成的字符串S,重复进行以下操作,直到字符串中不再有相邻的重复字符:在字符串中找到相邻的重复字符并将其删除。
示例:
输入:S = "abbaca" 输出:"ca" 解释:在字符串中,字符'a'重复2次,删除这两个字符后,得到最终结果为"ca"。
输入:S = "azxxzy" 输出:"ay" 解释:在字符串中,字符'z'重复2次,删除这两个字符后,得到"axy",字符'x'重复2次,删除这两个字符后,得到最终结果为"ay"。
1)题目分析与解题步骤:
这个问题可以使用栈来解决。我们可以遍历字符串中的每个字符,然后使用一个栈来模拟删除相邻重复字符的过程。对于每个字符,我们将其与栈顶元素比较,如果相同,则将栈顶元素出栈,表示删除这对相邻重复字符;如果不同,则将当前字符入栈。
解题步骤如下:
创建一个栈stack,用于模拟删除相邻重复字符的过程。
遍历字符串S中的每个字符,并执行以下操作:
如果栈为空或当前字符与栈顶元素不同,则将当前字符入栈。
如果当前字符与栈顶元素相同,则将栈顶元素出栈。
遍历完整个字符串后,栈中剩余的字符即为最终结果。
将栈中的字符按照出栈的顺序组合成字符串,并返回最终结果。
2)JavaScript解题框架:
function removeDuplicates(S) { let stack = new Stack(); for (let i = 0; i < S.length; i++) { let char = S.charAt(i); if (stack.isEmpty() || char !== stack.peek()) { stack.push(char); } else { stack.pop(); } } let result = ''; while (!stack.isEmpty()) { result = stack.pop() + result; } return result; }
在这个框架中,我们首先定义了一个栈类Stack,其中包含了常用的栈操作方法。然后,我们使用栈来删除字符串中的所有相邻重复项。
在removeDuplicates函数中,我们遍历字符串S,并使用栈来模拟删除相邻重复字符的过程。对于每个字符,我们将其与栈顶元素比较,如果相同,则将栈顶元素出栈,表示删除这对相邻重复字符;如果不同,则将当前字符入栈。
7.移除最外层的括号
给定一个有效的括号字符串S,移除字符串中最外层的括号,返回新的字符串。
示例:
输入:S = "(()())(())" 输出:"()()()" 解释:最外层的括号被移除,得到新的字符串为"()()()"。
输入:S = "(()())(())(()(()))" 输出:"()()()()(())" 解释:最外层的括号被移除,得到新的字符串为"()()()()(())"。
1)题目分析与解题步骤:
这个问题可以使用栈来解决。我们可以遍历字符串中的每个字符,然后使用一个栈来模拟括号的匹配过程。对于每个字符,如果它是左括号且栈为空,说明它是最外层的左括号,我们将其标记为不需要保留。否则,我们将其入栈,表示保留该括号。当遇到右括号时,我们将栈顶的左括号出栈,表示匹配成功。最后,将栈中剩余的括号组合成新的字符串即为最终结果。
解题步骤如下:
创建一个栈stack,用于模拟括号的匹配过程。
创建一个空字符串result,用于保存最终结果。
遍历字符串S中的每个字符,并执行以下操作:
如果当前字符是左括号且栈为空,说明它是最外层的左括号,不需要保留。
如果当前字符是左括号,将其入栈。
如果当前字符是右括号,将栈顶的左括号出栈,表示匹配成功。
如果出栈后,栈为空,说明这是最外层的右括号,不需要保留。
如果出栈后,栈不为空,将出栈的左括号和右括号添加到结果字符串result中。
返回结果字符串result作为最终的解答。
2)JavaScript解题框架:
function removeOuterParentheses(S) { let stack = new Stack(); let result = ''; for (let char of S) { if (char === '(' && stack.isEmpty()) { continue; } if (char === '(') { stack.push(char); } if (char === ')' && stack.peek() === '(') { stack.pop(); if (!stack.isEmpty()) { result += '(' + char + ')'; } } } return result; }
在这个框架中,我们首先定义了一个栈类Stack,其中包含了常用的栈操作方法。然后,我们使用栈来移除最外层的括号。
在removeOuterParentheses函数中,我们遍历字符串S,并使用栈来模拟括号的匹配过程。对于每个字符,我们根据括号的类型和栈的状态进行判断和操作,以移除最外层的括号。
最后,将栈中剩余的括号组合成新的字符串,并返回最终结果。
带你读《图解算法小抄》十七、栈(7)https://developer.aliyun.com/article/1348071?groupCode=tech_library