刷题笔记day11

笔记day11"/>

刷题笔记day11

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)