字符串匹配

题目来源

LeetCode 844. Backspace String Compare

精简解题

  1. 字符串入栈

  2. 遇到井号，提取栈顶元素

  3. 栈为空，不操作

  4. 判断两个字符串处理后是否一致

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    func backspaceCompare(S string, T string) bool {
	s := helper(S)
	t := helper(T)
	return s == t
}

//使用字符串回退作为栈的操作
func helper(S string) string {
	tmp := []byte{}
	for i := 0; i < len(S); i++ {
		if S[i] != '#' {
			tmp = append(tmp, S[i])
			continue
		}
		if len(tmp) > 0 {
			tmp = tmp[:len(tmp)-1]
		}
	}
	return string(tmp)
}

用栈实现队列

题目来源

LeetCode 232. Implement Queue using Stacks

解法

  1. 两个栈，数据栈和辅助栈

  2. 新数据输入，进入数据栈

  3. 数据输出，从辅助栈顶取

  4. 辅助栈为空时，数据栈导入辅助栈

     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

    type MyQueue struct {
	input  []int
	output []int
}

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

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

/** Removes the element from in front of queue and returns that element. */
func (q *MyQueue) Pop() int {
	q.Peek()
	element := q.output[len(q.output)-1]
	q.output = q.output[:len(q.output)-1]
	return element
}

/** Get the front element. */
func (q *MyQueue) Peek() int {
	if len(q.output) == 0 {
		for len(q.input) > 0 {
			q.output = append(q.output, q.input[len(q.input)-1])
			q.input = q.input[:len(q.input)-1]
		}
	}
	return q.output[len(q.output)-1]
}

/** Returns whether the queue is empty. */
func (q *MyQueue) Empty() bool {
	return len(q.input) == 0 && len(q.output) == 0
}

用队列实现栈

题目来源

Leetcode 225. Implement Stack using Queues

解法

  1. 两个队列，主队列和辅助队列

  2. 数据输入时，放入主队列

  3. 数据输出是，主队列元素输入到辅助队列，最后一个作为输出，不放入辅助队列

     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

    type MyStack struct {
	enque []int
	deque []int
}

/** Initialize your data structure here. */
func Constructor() MyStack {
	return MyStack{[]int{}, []int{}}
}

/** Push element x onto stack. */
func (this *MyStack) Push(x int) {
	this.enque = append(this.enque, x)
}

/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
	lenth := len(this.enque) - 1
	for i := 0; i < lenth; i++ {
		this.deque = append(this.deque, this.enque[0])
		this.enque = this.enque[1:]
	}
	top := this.enque[0]
	this.enque = this.deque
	this.deque = nil
	return top
}

/** Get the top element. */
func (this *MyStack) Top() int {
	top := this.Pop()
	this.enque = append(this.enque, top)
	return top
}

/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
	if len(this.enque) == 0 {
		return true
	}
	return false
}

括号字符串是否匹配

题目来源

LeetCode 20. Valid Parentheses

解法

  1. 经典的栈使用

  2. 遇到左边的括号符入栈

  3. 遇到右边的括号符，查找栈顶是否匹配

  4. 不匹配，返回false

  5. 最后栈空，则返回true

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    var m = map[uint8]uint8{')': '(', '}': '{', ']': '['}

func isValid(s string) bool {
	var stack []uint8
	for i := range s {
		if s[i] == '(' || s[i] == '{' || s[i] == '[' {
			stack = append(stack, s[i])
		} else {
			if len(stack) == 0 {
				return false
			}
			if m[s[i]] == stack[len(stack)-1] {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	if len(stack) == 0 {
		return true
	}
	return false
}