我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

leetcode-栈相关习题

发表于 2021-07-08 | 0 | 阅读次数 341

232.用栈实现队列

image.png
代码:

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
}

思路:

  1. 栈为先进后出,队列为先进先出。将一个栈的数据导入到另个栈时,再从另个栈pop,pop的数据就是原先栈中最先进的。
  2. 只有当第二个栈没有元素时,才去第一个栈导,不然顺序会错乱
  3. 一个栈导到第二个栈时,需要把所有元素导过去,而不是只导一个,这样就能保证,过去的这一批是按顺序的
  4. 两个栈push和pop的时候,要真实的将数据pop掉

150.逆波兰表达式求值

image.png

代码:

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]
}

思路:
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:

  1. 如果遇到操作数,则将操作数入栈;

  2. 如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。

注意:

  1. 使用strconv.Atoi来判断是数字还是符号
  2. 运算符运算的时候,要先将两操作数Pop掉,再进行append操作
  3. 切片[:len(stack)-1]为pop最后一个,[:len(stack)-2]为pop最后两个

20.有效的括号

image.png

代码:

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
}

思路:

  1. 判断右括号的情况,如果是左括号则加入栈中,如果是右括号就必须和栈顶的括号匹配上,不匹配上就false
  2. 最后栈里的长度为0
  3. 如果字符串长度为奇数则直接false
  4. 字符串循环,使用下标,则为byte类型,如果是range来遍历则为rune类型需要类型转换

1472.设计浏览器历史记录

image.png

代码:

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]
}

思路:

  1. 使用两个栈分别保存后退和前进的记录
  2. 前进和后退可以传steps,需要使用循环
  3. visit会清空前进的记录,判断后退和前进时先判断栈中的长度

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

image.png

代码:

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. 使用计数来判断和上个元素是否一致,若不一致则为1,一致则累加
  2. 移除指定位置的元素i与k的关系,不需要变量
  3. 设置标志,作为判断的条件

981.基于时间的键值存储

image.png

代码:

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 ""

}

思路:

  1. key有多个肯定是map的数据结构,这样get的时间复杂度为O(1)
  2. set时的timestamp是递增的,这样无形的帮你排好了序,可以直接使用切片
  3. 查找需要,找到满足条件的最大的那个timestamp,这必须要使用二分查找,不然不满足时间复杂度
  4. set的时候,map的key的数据类型切片是固定的,不需要判断key是否存在,可以直接append
  5. sort包里的search直接有内置的二分查找,它会直接返回满足条件最大的那个在切片中的序号(比下标大1),如果为0是查找失败
  6. sort中search函数中的匿名函数,是二分查找中,中间值的值大于目标值的情况(也就是if a[mid] > target 返回true)
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/leetcode-栈相关
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
leetcode链表相关
队列
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号