山西商城网站建设中国建设银行招聘官网

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

 方法一：使用容易理解的栈

思路：

1.将字符串转换为字符数组，依次遍历

2.创建栈

3.开始栈中为空，将字符压栈。

4.将待压入栈的字符与栈顶元素比较，相同时将栈顶元素弹出，不同时将待压栈字符压栈。

5.遍历结束，返回栈中元素的倒序。

class Solution {public String removeDuplicates(String s) {if (s==null||s.length()<=1){return s;}char[] chars = s.toCharArray();Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {if (!stack.isEmpty()&&stack.peek()==chars[i]){stack.pop();}else{stack.push(chars[i]);}}StringBuilder res = new StringBuilder();while (!stack.isEmpty()){res.append(stack.pop());}return String.valueOf(res.reverse());
//两种都可以// while (!stack.isEmpty()){//   res.insert(0,stack.pop());//   }//return String.valueOf(res);}
}

 注：
StringBuffer.insert: 在指定位置把任意类型的数据插入到字符串缓冲区里面，并返回字符串本身。

方法二：使用数组

思路：两个索引，一个索引遍历j，一个索引比较i，当相同时，将遍历索引后的字符覆盖相同的字符，更新字符串，详细步骤如下图：

 

        public String removeDuplicates(String s) {if (s==null||s.length()<=1){return s;}char[] chars = s.toCharArray();int i = 0;for (int j =1; j < chars.length; j++) {if (i==-1||chars[i]!=chars[j]){chars[++i]=chars[j];}else {i--;}}return  new String(Arrays.copyOfRange(chars,0,i+1));

 注：

Arrays.copyOfRange是一个数组拷贝方法，可以将一个数组中的一部分拷贝到一个新数组中。

int[] original = new int[] {1, 2, 3, 4, 5};
int[] copied = Arrays.copyOfRange(original, start, end);

 original拷贝的源数组，start是拷贝的起始位置（包含），end是拷贝的结束位置（不包含）。