232.用栈实现队列
代码:
type MyQueue struct {
StackA []int
StackB []int
}
/** Initialize your data structure here. */
func Constructor() MyQueue {
return MyQueue{}
}
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
this.StackA = append(this.StackA,x)
}
func (this *MyQueue)in2out(){
for len(this.StackA) > 0 {
this.StackB = append(this.StackB,this.StackA[len(this.StackA)-1])
this.StackA = this.StackA[:len(this.StackA)-1]
}
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
for len(this.StackB) == 0{
this.in2out()
}
ret := this.StackB[len(this.StackB)-1]
this.StackB = this.StackB[:len(this.StackB)-1]
return ret
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
if len(this.StackB) == 0{
this.in2out()
}
return this.StackB[len(this.StackB)-1]
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return len(this.StackA) == 0 && len(this.StackB ) == 0
}
思路:
- 栈为先进后出,队列为先进先出。将一个栈的数据导入到另个栈时,再从另个栈pop,pop的数据就是原先栈中最先进的。
- 只有当第二个栈没有元素时,才去第一个栈导,不然顺序会错乱
- 一个栈导到第二个栈时,需要把所有元素导过去,而不是只导一个,这样就能保证,过去的这一批是按顺序的
- 两个栈push和pop的时候,要真实的将数据pop掉
150.逆波兰表达式求值
代码:
func evalRPN(tokens []string) int {
stack := []int{}
for _,item := range tokens{
num,err := strconv.Atoi(item)
if err == nil{
stack = append(stack,num)
continue
}
lenStack := len(stack)
num1,num2 := stack[lenStack - 2 ],stack[lenStack - 1]
stack = stack[:lenStack-2]
switch item {
case "+":
ret := num1 + num2
stack = append(stack,ret)
case "-":
ret := num1 - num2
stack = append(stack,ret)
case "*":
ret := num1 * num2
stack = append(stack,ret)
case "/":
ret := num1 / num2
stack = append(stack,ret)
}
}
return stack[0]
}
思路:
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:
-
如果遇到操作数,则将操作数入栈;
-
如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。
注意:
- 使用strconv.Atoi来判断是数字还是符号
- 运算符运算的时候,要先将两操作数Pop掉,再进行append操作
- 切片[:len(stack)-1]为pop最后一个,[:len(stack)-2]为pop最后两个
20.有效的括号
代码:
func isValid(s string) bool {
n := len(s)
if n % 2 == 1 {
return false
}
pairs := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
stack := []byte{}
for i := 0; i < n; i++ {
if pairs[s[i]] > 0 {
if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, s[i])
}
}
return len(stack) == 0
}
思路:
- 判断右括号的情况,如果是左括号则加入栈中,如果是右括号就必须和栈顶的括号匹配上,不匹配上就false
- 最后栈里的长度为0
- 如果字符串长度为奇数则直接false
- 字符串循环,使用下标,则为byte类型,如果是range来遍历则为rune类型需要类型转换
1472.设计浏览器历史记录
代码:
type BrowserHistory struct {
stackA []string
stackB []string
}
func Constructor(homepage string) BrowserHistory {
return BrowserHistory{
stackA:[]string{homepage},
stackB:[]string{},
}
}
func (this *BrowserHistory) Visit(url string) {
this.stackA = append(this.stackA,url)
this.stackB = []string{}
}
func (this *BrowserHistory) Back(steps int) string {
for i:=0;i<steps;i++{
if len(this.stackA) == 1{
return this.stackA[0]
}
tem := this.stackA[len(this.stackA)-1]
this.stackB = append(this.stackB,tem)
this.stackA = this.stackA[:len(this.stackA)-1]
}
return this.stackA[len(this.stackA)-1]
}
func (this *BrowserHistory) Forward(steps int) string {
for i:=0;i<steps;i++{
if len(this.stackB) == 0{
return this.stackA[len(this.stackA)-1]
}
temp := this.stackB[len(this.stackB)-1]
this.stackA = append(this.stackA,temp)
this.stackB = this.stackB[:len(this.stackB)-1]
}
return this.stackA[len(this.stackA)-1]
}
思路:
- 使用两个栈分别保存后退和前进的记录
- 前进和后退可以传steps,需要使用循环
- visit会清空前进的记录,判断后退和前进时先判断栈中的长度
1209.删除字符串中的所有相邻重复项
代码:
func loop(s string,k int)string{
have = false
for i,num:=1,1;i<len(s);i++{
if s[i] != s[i-1]{
num = 1
}else{
num ++
if num == k{
s = s[:i-k+1]+s[i+1:]
have = true
break
}
}
}
return s
}
var have bool
func removeDuplicates(s string, k int) string {
for {
s= loop(s,k)
if !have {
return s
}
}
}
思路:
- 使用计数来判断和上个元素是否一致,若不一致则为1,一致则累加
- 移除指定位置的元素i与k的关系,不需要变量
- 设置标志,作为判断的条件
981.基于时间的键值存储
代码:
import "sort"
type pair struct{
timestamp int
value string
}
type TimeMap struct {
key map[string][]pair
}
/** Initialize your data structure here. */
func Constructor() TimeMap {
return TimeMap{
key:make(map[string][]pair),
}
}
func (this *TimeMap) Set(key string, value string, timestamp int) {
this.key[key] = append(this.key[key],pair{
timestamp:timestamp,
value:value,
})
}
func (this *TimeMap) Get(key string, timestamp int) string {
pairs := this.key[key]
i := sort.Search(len(pairs), func(i int) bool { return pairs[i].timestamp > timestamp })
if i > 0 {
return pairs[i-1].value
}
return ""
}
思路:
- key有多个肯定是map的数据结构,这样get的时间复杂度为O(1)
- set时的timestamp是递增的,这样无形的帮你排好了序,可以直接使用切片
- 查找需要,找到满足条件的最大的那个timestamp,这必须要使用二分查找,不然不满足时间复杂度
- set的时候,map的key的数据类型切片是固定的,不需要判断key是否存在,可以直接append
- sort包里的search直接有内置的二分查找,它会直接返回满足条件最大的那个在切片中的序号(比下标大1),如果为0是查找失败
- sort中search函数中的匿名函数,是二分查找中,中间值的值大于目标值的情况(也就是if a[mid] > target 返回true)