[代码随想录]Day10-栈与队列part02
题目：20. 有效的括号
思路：
很简单的一个栈的题目：
- 如果是左括号就存
- 如果是右括号就和栈顶的匹配
- 匹配失败就返回false
- 匹配成功就删除栈顶元素
- 如果结束后是空就说明匹配完成
这里需要注意的一个点是可以用map来代替过多的if else，希望能学会！
代码：
var pairs = map[byte]byte { // 做一个映射存储方便
')' : '(',
']' : '[',
'}' : '{',
}
func isValid(s string) bool {
stack := []byte{}
lens := 0 // 可以不用频繁的查询len(stack)
for i:=0; i < len(s); i++ {
if s[i] == '[' || s[i] == '{' || s[i] == '(' { // 左括号存
stack = append(stack, s[i])
lens++
}else if lens != 0 && stack[lens-1] == pairs[s[i]] { // 右括号匹配成功就删
stack = stack[:lens-1]
lens--
}else { // 匹配失败就false
return false
}
}
return lens == 0 // 是0才能true，因为可能剩下左括号
}
参考：
代码随想录
题目：1047. 删除字符串中的所有相邻重复项
思路：
和上面的题目一样都是匹配的问题，直接看注释
代码：
func removeDuplicates(s string) string {
stack := []byte{}
lens := 0
for i := 0; i < len(s); i++ {
if lens == 0 { // 如果还没有元素就直接添加
stack = append(stack, s[i])
lens++
}else if stack[lens-1] == s[i] { // 和上一个元素相同就删
stack = stack[:lens-1]
lens--
}else { // 和上一个不同就加
stack = append(stack, s[i])
lens++
}
}
return string(stack) // 转string类型
}
参考：
代码随想录
题目：150. 逆波兰表达式求值
思路：
题目不是很难，我要在这里学会的是如何去简化或者说提高代码的扩展性，比如对于运算符的判断以及对于加减乘除的计算。
详细看注释
代码：
var isOper = map[string]bool { // 判断是不是运算符
"+" : true,
"-" : true,
"*" : true,
"/" : true,
}
func evalRPN(tokens []string) int {
number := []int{}
lens := 0
for _, v := range tokens {
if _, ok := isOper[v]; ok { // 是运算符就操作
a := number[lens-2] // 取出倒数第二个数
b := number[lens-1] // 取出倒数第一个数
number[lens-2] = Calc(a, b, v) // 把结果存在倒数第二个位置
number = number[:lens-1] // 删除倒数第一个位置
lens-- // 元素-1
}else {
t, _:= strconv.Atoi(v) // string转int
number = append(number, t) // 添加到数字中
lens++ // 元素+1
}
}
return number[0] // 最后剩下一个元素就是结果
}
func Calc(a,b int, op string) int { // 根据运算符进行运算
if op == "+" {
return a + b
}else if op == "-" {
return a - b
}else if op == "*" {
return a * b
}else if op == "/" {
return a / b
}
return 0
}
参考：
代码随想录