leetcode-栈相关习题 | 我命由我不由天

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）