代码随想录算法训练营第11天

20 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

思考：第一直觉是是使用双指针，考虑了一下，不容易按照顺序消除匹配的括号；看了解析后，现在回想还是记不住那三种情况，但是要记住前提是使用栈这种类型的数据结构，现用map（dict）形式将 右括号：左括号存入，如果token是左括号则存入栈，如果是右括号，判断栈顶元素是不是等于右括号对应的左括号，如果是，弹出栈顶元素，如果不是返回false。循环结束后，如果栈中还有元素则返回false。

func isValid(s string) bool {
    dic := map[byte]byte{')':'(', '}':'{', ']':'['}
    ls := make([]byte,0)
    if s ==""{
        return true
    }
    for i:=0;i<len(s);i++{
        if s[i] == '(' || s[i] == '[' || s[i] == '{'{
            ls = append(ls, s[i])
        }else if dic[s[i]] == ls[len(ls)-1]{
            ls = ls[:len(ls)-1]
        }else{
            return false
        }
    }
    return len(ls) == 0
}

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思考：题目中是两个相邻且相同的字母，那么按照栈的特性，直接判断栈顶元素是不是和遍历到的元素相同就行了，相同则pop栈顶元素即可。

func removeDuplicates(s string) string {
    stack := []byte{}
    for i := 0; i<len(s); i++{
        if len(stack)>0 && s[i] == stack[len(stack)-1]{
            stack = stack[:len(stack)-1]
        }else{
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

150 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

思考：理解完“波兰表示法”后，遍历列表，遇到数字存入栈中，遇到算数运算符时提取出栈顶两个数字，做完运算后，存入栈中。

func evalRPN(tokens []string) int {
    stack := []int{}
    for _, token := range tokens{
        val, err := strconv.Atoi(token) // 提取数字，不是数字返回非nil的err
        if err == nil{
            stack = append(stack, val)
        }else{
            num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
            stack = stack[:len(stack)-2]
            switch token{
                case "+":
                stack = append(stack, num1 + num2)
                case "-":
                stack = append(stack, num1 - num2)
                case "*":
                stack = append(stack, num1 * num2)
                case "/":
                stack = append(stack, num1 / num2)
            }
        }
    }
    return stack[0]
}