【代码随想录】算法训练计划11

1、20. 有效的括号

题目：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路：

• 注意for range 的v 和s[i] 类型是不同的即可

func isValid(s string) bool {// 代码一刷map1 := map[rune]rune {')' : '(','}' : '{',']' : '[',}stack1 := make([]rune, 0)for _,v := range s {if len(stack1) > 0 && map1[v] != ' ' && stack1[len(stack1)-1] == map1[v] {stack1 = stack1[:len(stack1)-1]} else {stack1 = append(stack1, v)}}if len(stack1) == 0 {return true}return false
}

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

题目：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路：

• go for range时候把它当成rune了，就uint32
• 想邻的

func removeDuplicates(s string) string {// 代码一刷stack := make([]rune, 0)for _,v := range s {if len(stack) > 0 && v == stack[len(stack)-1] {stack = stack[: len(stack)-1]} else {stack = append(stack, v)}}return string(stack)
}

3、150. 逆波兰表达式求值

题目：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

思路：

• Atoi i 代表 int
• 遇见算数符号，，就将前两位数字运算结果代替前两位数字，即可

func evalRPN(tokens []string) int {// 代码一刷stack := make([]int, 0)for _,v := range tokens {if v != "+" && v != "-" && v != "*" && v != "/" {val, _ := strconv.Atoi(v)stack = append(stack, val)} else {switch v {case "+":val := stack[len(stack)-1] + stack[len(stack)-2]stack = stack[:len(stack)-2]stack = append(stack, val)case "-":val := stack[len(stack)-2] - stack[len(stack)-1]stack = stack[:len(stack)-2]stack = append(stack, val)case "*":val := stack[len(stack)-2] * stack[len(stack)-1]stack = stack[:len(stack)-2]stack = append(stack, val)case "/":val := stack[len(stack)-2] / stack[len(stack)-1]stack = stack[:len(stack)-2]stack = append(stack, val)}}}return stack[0]
}