package a20_有效的括号.极客时间;

public class Solution {

public boolean isValid(String s) {

int length;

do {

length = s.length();

s = s.replace("()", "").replace("{}", "").replace("[]", "");

} while (length != s.length());

return s.length() == 0;

}

public static void main(String[] args) {

new Solution().isValid("{()}");

}

}

package a20_有效的括号.题解;

import java.util.HashMap;

import java.util.Stack;

public class Solution {

// Hash table that takes care of the mappings. 负责映射的哈希表。

private HashMap<Character, Character> mappings;

// Initialize hash map with mappings. This simply makes the code easier to read.

// 使用映射初始化h ash map。这简单地方式使代码更容易阅读。

public Solution() {

this.mappings = new HashMap<Character, Character>();

this.mappings.put(')', '(');

this.mappings.put('}', '{');

this.mappings.put(']', '[');

}

public boolean isValid(String s) {

// Initialize a stack to be used in the algorithm. 初始化一个栈

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

// If the current character is a closing bracket. 如果当前字符是结束括号

if (this.mappings.containsKey(c)) {

// Get the top element of the stack. If the stack is empty, set a dummy value of '#'

// 获取栈的顶部元素。如果栈为空，请设置虚拟值“＃”

char topElement = stack.empty() ? '#' : stack.pop();

// If the mapping for this bracket doesn't match the stack's top element, return false.

// 如果此括号的映射与栈的top元素不匹配，则返回false。

if (topElement != this.mappings.get(c)) return false;

} else {

// If it was an opening bracket, push to the stack. 如果它是一个左括号，推到栈。

stack.push(c);

}

}

// If the stack still contains elements, then it is an invalid expression.

// 如果栈仍然包含元素，那么它是一个无效的表达式。

return stack.isEmpty();

}

}

**思路**

想象一下，你正在为你的大学课设编写一个小型编译器，编译器的任务之一（或称子任务）将检测括号是否匹配。

我们本文中看到的算法可用于处理编译器正在编译的程序中的所有括号，并检查是否所有括号都已配对。这将检查给定的括号字符串是否有效，是一个重要的编程问题。

我们这个问题中将要处理的表达式可以包含以下三种不同类型的括号：

- `()`，

- `{}` 以及

- `[]`

在查看如何检查由这些括号组成的给定表达式是否有效之前，让我们看一下该问题的简化版本，在简化后的问题中，只含一种类型的括号。这么一来，我们将会遇到的表达式是

上我们试着用一个简单的算法来解决这一问题。

1. 我们从表达式的左侧开始，每次只处理一个括号。

2. 假设我们遇到一个开括号（即 `(`），表达式是否无效取决于在该表达式的其余部分的某处是否有相匹配的闭括号（即 `)`）。此时，我们只是增加计数器的值保持跟踪现在为止开括号的数目。`left += 1`

3. 如果我们遇到一个闭括号，这可能意味着这样两种情况：

1. 此闭括号没有与与之对应的开括号，在这种情况下，我们的表达式无效。当 `left == 0`，也就是没有未配对的左括号可用时就是这种情况。

2. 我们有一些未配对的开括号可以与该闭括号配对。当 `left > 0`，也就是有未配对的左括号可用时就是这种情况。

4. 如果我们在 `left == 0` 时遇到一个闭括号（例如 `)`），那么当前的表达式无效。否则，我们会减少 `left` 的值，也就是减少了可用的未配对的左括号的数量。

5. 继续处理字符串，直到处理完所有括号。

6. 如果最后我们仍然有未配对的左括号，这意味着表达式无效。

在这里讨论这个特定算法是因为我们从该解决方案中获得灵感以解决原始问题。为了更好地理解我们讨论的算法，请观看下面的动画演示。

如果我们只是尝试对原始问题采用相同的办法，这是根本就行不通的。基于简单计数器的方法能够在上面完美运行是因为所有括号都具有相同的类型。因此，当我们遇到一个闭括号时，我们只需要假设有一个对应匹配的开括号是可用的，即假设 `left > 0`。

但是，在我们的问题中，如果我们遇到 `]`，我们真的不知道是否有相应的 `[` 可用。你可能会问：

这可能不起作用，因为括号的相对位置在这里也很重要。例如：

如果我们只是在这里维持计数器，那么只要我们遇到闭合方括号，我们就会知道此处有一个可用的未配对的开口方括号。但是，**最近的未配对的开括号是一个花括号，而不是一个方括号**，因此计数方法在这里被打破了。

关于有效括号表达式的一个有趣属性是有效表达式的子表达式也应该是有效表达式。（不是每个子表达式）例如

此外，如果仔细查看上述结构，颜色标识的单元格将标记开闭的括号对。整个表达式是有效的，而它的子表达式本身也是有效的。这为问题提供了一种递归结构。例如，考虑上图中两个绿色括号内的表达式。开括号位于索引 `1`，相应闭括号位于索引 `6`。

让我们看看下面的这个想法，从整体表达式中一次删除一个较小的表达式，因为这是一个有效的表达式，我们最后剩留下一个空字符串。

让我们看看使用栈作为该问题的中间数据结构的算法。

**算法**

1. 初始化栈 S。

2. 一次处理表达式的每个括号。

3. 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 **子表达式**。

4. 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 `相同类型的` 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。

5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

我们来看一下该算法的动画演示，然后转到实现部分。

现在让我们看看该算法是如何实现的。

public class Solution {

// Hash table that takes care of the mappings. 负责映射的哈希表。

private HashMap<Character, Character> mappings;

// Initialize hash map with mappings. This simply makes the code easier to read.

// 使用映射初始化h ash map。这简单地方式使代码更容易阅读。

public Solution() {

this.mappings = new HashMap<Character, Character>();

this.mappings.put(')', '(');

this.mappings.put('}', '{');

this.mappings.put(']', '[');

}

public boolean isValid(String s) {

// Initialize a stack to be used in the algorithm. 初始化一个栈

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

// If the current character is a closing bracket. 如果当前字符是结束括号

if (this.mappings.containsKey(c)) {

// Get the top element of the stack. If the stack is empty, set a dummy value of '#'

// 获取栈的顶部元素。如果栈为空，请设置虚拟值“＃”

char topElement = stack.empty() ? '#' : stack.pop();

// If the mapping for this bracket doesn't match the stack's top element, return false.

// 如果此括号的映射与栈的top元素不匹配，则返回false。

if (topElement != this.mappings.get(c)) return false;

} else {

// If it was an opening bracket, push to the stack. 如果它是一个左括号，推到栈。

stack.push(c);

}

}

// If the stack still contains elements, then it is an invalid expression.

// 如果栈仍然包含元素，那么它是一个无效的表达式。

return stack.isEmpty();

}

}

**复杂度分析**

- 时间复杂度：O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1) 的推入和弹出操作。

- 空间复杂度：O(n)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 `((((((((((`。

public class Solution {

public boolean isValid(String s) {

int length;

do {

length = s.length();

s = s.replace("()", "").replace("{}", "").replace("[]", "");

} while (length != s.length());

return s.length() == 0;

}

}

**复杂度分析**

- 时间复杂度：O(n^2 / 2)

相同点：大家都返回栈顶的值。

不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。

package a232_用栈实现队列.解法1;

import java.util.Stack;

public class MyQueue {

private Stack<Integer> s1 = new Stack<>();

private Stack<Integer> s2 = new Stack<>();

/** Initialize your data structure here. */

public MyQueue() {

}

/** Push element x to the back of queue. */

public void push(int x) {

while (!s1.isEmpty())

s2.push(s1.pop());

s2.push(x);

while (!s2.isEmpty())

s1.push(s2.pop());

}

/** Removes the element from in front of queue and returns that element. */

public int pop() {

return s1.pop();

}

/** Get the front element. 获取头元素 */

public int peek() {

return s1.peek();

}

/** Returns whether the queue is empty. */

public boolean empty() {

return s1.isEmpty();

}

}

package a232_用栈实现队列.解法2;

import java.util.Stack;

public class MyQueue {

private Stack<Integer> s1 = new Stack<>();

private Stack<Integer> s2 = new Stack<>();

private int front;

/** Initialize your data structure here. */

public MyQueue() {

}

/** Push element x to the back of queue. */

public void push(int x) {

if (s1.empty())

front = x;

s1.push(x);

}

/** Removes the element from in front of queue and returns that element. */

public int pop() {

if (s2.isEmpty()) {

while (!s1.isEmpty())

s2.push(s1.pop());

}

return s2.pop();

}

/** Get the front element. */

public int peek() {

if (!s2.isEmpty()) {

return s2.peek();

}

return front;

}

/** Returns whether the queue is empty. */

public boolean empty() {

return s1.isEmpty() && s2.isEmpty();

}

}