LeetCode【每日一题】-栈和队列2

有效的括号

题目链接

思路：运用入栈出栈操作（注意当字符串遍历完成且栈为空才匹配成功）
1、当遇到左括号的时，则入栈相应地右括号
2、否则当当前栈不为空且字符串没遍历完成或是字符串没遍历完当前字符不等栈顶字符则匹配不成功
3、否则出栈
4、遍历完成后当栈为空返回true，否则false

import java.util.Stack;

/**
 * 题目链接：https://leetcode.cn/problems/valid-parentheses/
 * > 思路：运用入栈出栈操作（注意当字符串遍历完成且栈为空才匹配成功）
 * >      1、当遇到左括号的时，则入栈相应地右括号
 * >      2、否则当当前栈不为空且字符串没遍历完成或是字符串没遍历完当前字符不等栈顶字符则匹配不成功
 * >      3、否则出栈
 * >      4、遍历完成后当栈为空返回true，否则false
 */
public class LeetCode20 {
    public boolean isValid(String s) {
        //创建一个栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.peek() != ch) {
                return false;
            } else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

题目链接

思路：运用对对碰，如果相同的元素放在挨在一起就要消除（栈）
1、遍历字符串，当栈为空时或是当前元素与栈顶元素不同则入栈
2、否则出栈
3、遍历完字符串栈中的元素即为结果

解法一（栈）

    public String removeDuplicates(String s) {
        //创建一个栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //若栈为空或是当前元素与栈顶元素不同入栈
            if (stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else {
                stack.pop();
            }
        }
        String sb = "";
        //因为栈的先进后出特性，反向拼接字符串
        while (!stack.isEmpty()) {
            sb = stack.pop() + sb;
        }
        return sb;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解法二（用字符串模拟栈）

    /**
     * 利用字符串来模拟栈
     * @param s
     * @return
     */
    public String removeDuplicates2(String s) {
        StringBuilder sb = new StringBuilder();
        int index = -1;
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (index == -1 || ch != sb.charAt(index)) {
                sb.append(ch);
                index++;
            } else {
                sb.deleteCharAt(index);
                index--;
            }
        }
        return sb.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法三（双指针）

    /**
     * 双指针:
     *  可以理解为，慢指针为一个新字符串，快指针遍历原字符串
     * @param s
     * @return
     */
    public String removeDuplicates3(String s) {
        //定义快慢指针
        int low = 0;
        int fast = 0;
        //转化为字符数组
        char[] arr = s.toCharArray();
        while (fast < s.length()) {
            arr[low] = arr[fast];

            //判断是否有相邻元素相同
            if (low >= 1 && arr[low] == arr[low - 1]) {
                //回退一个字符
                low--;
            } else {
                low++;
            }
            fast++;
        }
        return new String(arr, 0, low);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26