IT博客汇 | 『代码随想录』栈与队列（Stack & Queue）

『代码随想录』栈与队列（Stack & Queue）

NX の博客发表于 2023-11-03 02:43:22

DAY 10

232.用栈实现队列

因为栈和队列的出队顺序是反的，所以再来个栈倒腾一下就是正的了

type MyQueue struct {
    in  []int
    out []int
}

func Constructor() MyQueue {
    return MyQueue{
        in:  []int{},
        out: []int{},
    }
}

func (this *MyQueue) Push(x int) {
    this.in = append(this.in, x)
}

func (this *MyQueue) shift() { // 倒腾一下
    for len(this.in) != 0 {
        this.out = append(this.out, this.in[len(this.in)-1])
        this.in = this.in[:len(this.in)-1]
    }
}

func (this *MyQueue) Pop() int {
    if len(this.out) == 0 {
        this.shift()
    }
    ans := this.out[len(this.out)-1]
    this.out = this.out[:len(this.out)-1]
    return ans
}

func (this *MyQueue) Peek() int {
    if len(this.out) == 0 {
        this.shift()
    }
    return this.out[len(this.out)-1]
}

func (this *MyQueue) Empty() bool {
    return len(this.in) == 0 && len(this.out) == 0
}

225.用队列实现栈

一个队列就够了

出栈的话，把前 n-1 个元素扔到后面去（我称之为 shift 操作），当前元素就是刚入队的元素了

Top 的话就先出栈再放进去

type MyStack struct {
    q []int
}

func Constructor() MyStack {
    return MyStack{
        q: []int{},
    }
}

func (this *MyStack) Push(x int) {
    this.q = append(this.q, x)
}

func (this *MyStack) shift() { // 将前 n-1 个元素出队再加入
    n := len(this.q)
    for i := 0; i < n-1; i++ {
        this.q = append(this.q[1:], this.q[0])
    }
}

func (this *MyStack) Pop() int {
    this.shift()
    ans := this.q[0]
    this.q = this.q[1:]
    return ans
}

func (this *MyStack) Top() int {
    ans := this.Pop()
    this.Push(ans)
    return ans
}

func (this *MyStack) Empty() bool {
    return len(this.q) == 0
}

也可以换个思路，在 Push 的时候就 shift 也行，看上去更简单

type MyStack struct {
    q []int
}

func Constructor() MyStack {
    return MyStack{
        q: []int{},
    }
}

func (this *MyStack) Push(x int) {
    this.q = append(this.q, x)
    this.shift()
}

func (this *MyStack) shift() { // 将前 n-1 个元素出队再加入
    n := len(this.q)
    for i := 0; i < n-1; i++ {
        this.q = append(this.q[1:], this.q[0])
    }
}

func (this *MyStack) Pop() int {
    ans := this.q[0]
    this.q = this.q[1:]
    return ans
}

func (this *MyStack) Top() int {
    return this.q[0]
}

func (this *MyStack) Empty() bool {
    return len(this.q) == 0
}

DAY 11

20.有效的括号

经典的栈应用

func isValid(s string) bool {
    stack := []rune{}
    for _, c := range s {
        switch c {
        case '(', '[', '{':
            stack = append(stack, c)
        case ')':
            if len(stack) == 0 || stack[len(stack)-1] != '(' {
                return false
            }
            stack = stack[:len(stack)-1]
        case ']':
            if len(stack) == 0 || stack[len(stack)-1] != '[' {
                return false
            }
            stack = stack[:len(stack)-1]
        case '}':
            if len(stack) == 0 || stack[len(stack)-1] != '{' {
                return false
            }
            stack = stack[:len(stack)-1]
        }

    }

    if len(stack) != 0 {
        return false
    }

    return true
}

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

func removeDuplicates(s string) string {
    stack := []rune{}

    for _, c := range s {
        if len(stack) != 0 && c == stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }

    return string(stack)
}

150.逆波兰表达式求值

经典中的经典

func evalRPN(tokens []string) int {
    stack := []int{}
    for _, s := range tokens {
        n := len(stack)
        switch s {
        case "+":
            stack = append(stack[:n-2], stack[n-2]+stack[n-1])
        case "-":
            stack = append(stack[:n-2], stack[n-2]-stack[n-1])
        case "*":
            stack = append(stack[:n-2], stack[n-2]*stack[n-1])
        case "/":
            stack = append(stack[:n-2], stack[n-2]/stack[n-1])
        default:
            stack = append(stack, atoi(s))
        }
    }
    return stack[0]
}

func atoi(x string) int {
    opt, ans := 1, 0
    for _, c := range x {
        if c == '-' {
            opt = -1
            continue
        }
        ans = ans*10 + int(c-'0')
    }
    return ans * opt
}

DAY 12

周日休息

DAY 13

239.滑动窗口最大值

非常好的单调队列例题

单调队列，队列中从头到尾单调递减

Pop：传入当前窗口移动需要弹出的值，如果等于头元素则弹出
Push：在尾部尝试加入，如果遇到比当前元素小的都从尾部弹出
GetMax：取头元素

type MonoQ struct {
    data []int
}

func NewMonoQ() MonoQ {
    return MonoQ{
        data: []int{},
    }
}

// Pop 传入当前窗口移动需要弹出的值，如果等于头元素则弹出
func (q *MonoQ) Pop(x int) {
    if len(q.data) != 0 && x == q.data[0] {
        q.data = q.data[1:]
    }
}

// Push 传入当前窗口移动需要压入的值，如果大于尾元素则弹出尾元素，直到小于等于尾元素
func (q *MonoQ) Push(x int) {
    for len(q.data) != 0 && x > q.data[len(q.data)-1] {
        q.data = q.data[:len(q.data)-1]
    }
    q.data = append(q.data, x)
}

// GetMax 获取当前窗口最大值
func (q *MonoQ) GetMax() int {
    return q.data[0]
}

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    ans := []int{}
    q := NewMonoQ()
    for i := 0; i < k; i++ {
        q.Push(nums[i])
    }
    ans = append(ans, q.GetMax())
    for i := k; i < n; i++ {
        q.Pop(nums[i-k])
        q.Push(nums[i])
        ans = append(ans, q.GetMax())
    }
    return ans
}

347.前 K 个高频元素

两种方法，拿到频率的 map 之后用堆维护前 K 个，或者直接排序再取前 K 个

复习一下 Golang 里面的优先队列和排序

用惯了 C++ STL 的开箱即用的优先队列，我只能说 Golang 的优先队列真的不好用（

排序，记得导入 sort 包

使用内建的 Ints

1 2	nums := []int{4, 2, 3, 1} sort.Ints(nums)

使用 sort.Slice

1
2
3

sort.Slice(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})

优先队列，记得导入 heap 包

需要实现几个接口，在使用的时候，如果你是直接将一个切片转换成堆，需要使用 heap.Init

需要注意的是使用的时候不是面向对象的，你需要使用 heap.XX 来操作

元素仅为 int 的简单队列

type IntPriorityQueue []int

func (pq IntPriorityQueue) Len() int           { return len(pq) }
func (pq IntPriorityQueue) Less(i, j int) bool { return pq[i] < pq[j] }
func (pq IntPriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *IntPriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(int))
}

func (pq *IntPriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}

func main() {
pq := &IntPriorityQueue{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}

// 建立优先队列堆
heap.Init(pq)

// 向优先队列中添加元素
heap.Push(pq, 7)

// 从优先队列中按照优先级取出元素
for pq.Len() > 0 {
fmt.Printf("%d ", heap.Pop(pq))
}
}

根据结构体中的一个字段进行排序的队列

// Item 表示优先队列中的元素
type Item struct {
value    interface{} // 元素的值
priority int         // 优先级
}

// PriorityQueue 实现了heap.Interface接口
type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
// 这里我们使用优先级来决定元素的顺序，较小的优先级排在前面
return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
item := x.(Item)
*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}

func main() {
// 创建一个优先队列
pq := make(PriorityQueue, 0)

// 添加元素到优先队列
heap.Push(&pq, Item{value: "B", priority: 2})
heap.Push(&pq, Item{value: "C", priority: 1})
heap.Push(&pq, Item{value: "A", priority: 3})

// 从优先队列中按照优先级取出元素
for pq.Len() > 0 {
item := heap.Pop(&pq).(Item)
fmt.Printf("%s (priority: %d)\n", item.value, item.priority)
}
}

言归正传，本体的两种方法

直接排序

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)

    for _, v := range nums {
        m[v]++
    }

    count := make([][2]int, 0, len(m))
    for k, v := range m {
        count = append(count, [2]int{k, v})
    }

    sort.Slice(count, func(i, j int) bool {
        return count[i][1] > count[j][1]
    })

    ans := make([]int, 0, k)

    for i := 0; i < k; i++ {
        ans = append(ans, count[i][0])
    }
    return ans
}

还可以更简单

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for _, v := range nums {
        m[v]++
    }

    ans := make([]int, 0, len(m))
    for k, _ := range m {
        ans = append(ans, k)
    }

    sort.Slice(ans, func(i, j int) bool {
        return m[ans[i]] > m[ans[j]]
    })

    return ans[:k]
}

维护大顶堆

type Item struct {
    value int
    freq  int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq < pq[j].freq }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(Item)
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for _, num := range nums {
        m[num]++
    }

    pq := make(PriorityQueue, 0)
    for value, freq := range m {
        heap.Push(&pq, Item{value, freq})
        if pq.Len() > k {
            heap.Pop(&pq)
        }
    }

    ans := make([]int, k)
    for i := 0; i < k; i++ {
        item := heap.Pop(&pq).(Item)
        ans[i] = item.value
    }

    return ans
}