当前位置：首页 > news >正文

刷题笔记day11-栈与队列2

news 2025/8/9 15:27:27

20. 有效的括号

这个是典型的使用栈，来进行匹配。
因为栈是先进后出，所以，最近的左括号一定在栈顶。如果不是，则就是不匹配了。

func isValid(s string) bool {stack := Stack{}dict := map[byte]byte {')': '(',']': '[','}': '{',}for _, item := range []byte(s) {if leftVal, ok := dict[item]; ok {if stack.pop() != leftVal {return false}} else {stack.push(item)}}return stack.length == 0
}type Stack struct {data []bytelength int
}func (s *Stack) pop() (v byte) {if s.length < 1 {return }v = s.data[s.length-1]s.data = s.data[:s.length-1]s.length--return 
}func (s *Stack) push(v byte) {s.data = append(s.data, v)s.length++
}

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

func removeDuplicates(s string) string {// 思路：和栈顶不等的时候，s2 := []byte(s)stack := Stack{}stack.push(s2[0])for i := 1; i < len(s2); i++ {if v := stack.top(); v != s2[i] {stack.push(s2[i])} else {stack.pop()}}return string(stack.data)
}type Stack struct {data []bytelength int
}func (s *Stack) pop() (v byte) {if s.length < 1 {return }v = s.data[s.length-1]s.data = s.data[:s.length-1]s.length--return 
}func (s *Stack) top() (v byte) {if s.length < 1 {return }v = s.data[s.length-1]return 
}func (s *Stack) push(v byte) {s.data = append(s.data, v)s.length++
}

题目中是连续两个重复字符才删除，那么是多个重复字符如何删除呢？
可以增加一个last_char 变量，存放着上一次的结果。

s2 := []byte(s)
stack := Stack{}
stack.push(s2[0])
var lastChar = s2[0]
for i := 1; i < len(s2); i++ {v := stack.top()if v == s2[i] {stack.pop()} else if (v != lastChar) && (v != s2[i]) {// 和上一次字符相同时，不需要入栈stack.push(s2[i])}
}
return string(stack.data)

6. 逆波兰表达式求值

逆波兰表达式是一种后缀表达式，运算符号在后面，前面俩是运算数。

本质上还是使用栈来进行取值，然后运算。

import "strconv"func evalRPN(tokens []string) int {// 思路：符号就退出两个数字，然后运算既可stack := Stack{}var (s1 ints2 intresult int)for _, val := range tokens {if val == "+" || val == "-" || val == "*" || val == "/" {s2 = stack.pop()s1 = stack.pop()if val == "+" {stack.push(s1 + s2)} else if val == "-" {stack.push(s1 - s2)} else if val == "*" {stack.push(s1 * s2)} else if val == "/" {stack.push(s1 / s2)}} else {intVal, _ := strconv.Atoi(val)stack.push(intVal)}}result = stack.pop()return result
}type Stack struct {data []intlength int
}func (s *Stack) pop() (v int) {if s.length < 1 {return }v = s.data[s.length-1]s.data = s.data[:s.length-1]s.length--return 
}func (s *Stack) top() (v int) {if s.length < 1 {return }v = s.data[s.length-1]return 
}func (s *Stack) push(v int) {s.data = append(s.data, v)s.length++
}