网站开发数据库设计的作用,上海福州路附近做网站的公司,手机网站开发费用,新站网站推广该如何做Problem: 1047. 删除字符串中的所有相邻重复项 文章目录 思路解题方法复杂度Code 思路 最直观的思路就是比较当前字的字符和相邻#xff08;也包含删除后再相邻#xff09;的上一字符是否相同#xff0c;若相同则想办法去除两相同的字符#xff0c;而关键就在如何较为便捷的… Problem: 1047. 删除字符串中的所有相邻重复项 文章目录 思路解题方法复杂度Code 思路 最直观的思路就是比较当前字的字符和相邻也包含删除后再相邻的上一字符是否相同若相同则想办法去除两相同的字符而关键就在如何较为便捷的比较同时去除当前和相邻也包含删除后再相邻的上一个一样的字符。由此我们可以想到使用栈这一数据结构。 具体的 我们将字符串遍历若栈为空或者当前栈顶元素与当前的字符不匹配则把当前字符加入到栈否则出栈 解题方法 1.利用java双端队列模拟栈便于将后续剩余的元素直接取出转换成字符串。如果直接利用栈还会多一步将字符逆序的操作 2.遍历字符串用一个变量记录当前字符栈为空或者当前栈顶元素与当前的字符 不匹配则把当前字符加入到栈否则出栈在双端队列中在对尾操作. 3.取出双端队列中剩余元素利用StringBuilder将其拼接并最终转换为字符串。 复杂度
时间复杂度: 添加时间复杂度, 示例 O ( n ) O(n) O(n) 空间复杂度: 添加空间复杂度, 示例 O ( n ) O(n) O(n) Code class Solution {//Time Complexity: O(N)//Space Complexity: O(N)public String removeDuplicates(String s) {//使用双端队列模拟栈DequeCharacter deque new LinkedList();for (int i 0; i s.length(); i) {char c s.charAt(i);//如果栈顶元素和当前的字符不相同则入栈if (deque.isEmpty() || deque.peekLast() ! c) {deque.addLast(c);} else {deque.pollLast();}}//将栈中剩余的元素取出来StringBuilder sb new StringBuilder();while (!deque.isEmpty()) {sb.append(deque.pollFirst());}return sb.toString();}
}
