有效的括号

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1:

1
2
输入:s = "()"
输出:true

示例 2:

1
2
输入:s = "()[]{}"
输出:true

示例 3:

1
2
输入:s = "(]"
输出:false

示例 4:

1
2
输入:s = "([)]"
输出:false

示例 5:

1
2
输入:s = "{[]}"
输出:true

解题思路&题解

这道题和课堂例题没啥区别没啥好讲的,直接上代码:

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
func isValid(s string) bool {
if len(s)%2 == 1 {
return false
}
pars := []rune{
'(': ')',
'{': '}',
'[': ']',
}
stack := []rune{}
for _, c := range s {
if c == '(' || c == '{' || c == '[' {
stack = append(stack, c)
} else if len(stack) > 0 {
jugeCh := stack[len(stack)-1]
if c != pars[jugeCh] {
return false
}
stack = stack[:len(stack)-1]
} else {
return false
}
}
if len(stack) != 0 {
return false
}
return true
}

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

进阶:
你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]

解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

解题思路&题解

这里利用了两个栈,一个栈处理输入另一个处理输出(in和out)。
利用栈的特性,当输出栈为空时将输入栈的内容pop输出栈, 这样输出栈的顺序就是队列的顺序了!
代码如下:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
type MyQueue struct {
in, out []int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
return MyQueue{}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
this.in = append(this.in, x)
}

func (this *MyQueue) in2out() {
for len(this.in) > 0 {
this.out = append(this.out, this.in[len(this.in)-1])
this.in = this.in[:len(this.in)-1]
}
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
if len(this.out) == 0 {
// 将输入栈 弹出到输出栈中
this.in2out()
}
out := this.out[len(this.out)-1]
this.out = this.out[:len(this.out)-1]
return out
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
if len(this.out) == 0 {
// 将输入栈 弹出到输出栈中
this.in2out()
}
return this.out[len(this.out)-1]
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return len(this.in) == 0 && len(this.out) == 0
}

/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/