返回

栈与队列

用栈实现队列

232. 用栈实现队列 - 力扣(LeetCode)

用两个栈实现先入先出队列

在Go中用切片模拟栈,一个输入栈,一个输出栈

  • 入队:存入输入栈
  • 出队:弹出输出栈顶,若输出栈为空,将输入栈所有数据存入输出栈
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
type MyQueue struct {
    stackIn  []int // 输入栈
    stackOut []int // 输出栈
}

func Constructor() MyQueue {
    return MyQueue{
        stackIn:  make([]int, 0),
        stackOut: make([]int, 0),
    }
}

// 入队
func (this *MyQueue) Push(x int) {
    this.stackIn = append(this.stackIn, x) // 往输入栈追加
}

// 出队
func (this *MyQueue) Pop() int {
    if len(this.stackOut) == 0 { // 输出栈为空
        if len(this.stackIn) == 0 { // 输入栈也为空
            return -1
        }
        for i := len(this.stackIn) - 1; i >= 0; i-- { // 从输入栈顶逐个取元素存入输出栈
            this.stackOut = append(this.stackOut, this.stackIn[i]) // 输入栈元素存入输出栈
        }
        this.stackIn = []int{} // 清空输入栈
    }
    res := this.stackOut[len(this.stackOut)-1]           // 取出出栈元素
    this.stackOut = this.stackOut[:len(this.stackOut)-1] // 更新输出栈
    return res
}

// 获取队头值
func (this *MyQueue) Peek() int {
    res := this.Pop() // 出队
    if res == -1 {    // 队空
        return -1
    }
    this.stackOut = append(this.stackOut, res) // 放回输出栈
    return res
}

// 判队空
func (this *MyQueue) Empty() bool {
    return len(this.stackOut) == 0 && len(this.stackIn) == 0
}
  • 时间复杂度: push和empty为O(1),pop和peek为O(n)
  • 空间复杂度: O(n)

用队列实现栈

225. 用队列实现栈 - 力扣(LeetCode)

用两个队列实现一个后入先出(LIFO)的栈

其实这道题目就是用一个队列就够了,一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出对头元素就是栈的顺序了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
type MyStack struct {
    queue []int
}

func Constructor() MyStack {
    return MyStack{
        queue: make([]int, 0),
    }
}

// 进栈
func (this *MyStack) Push(x int) {
    this.queue = append(this.queue, x) // 追加到队列尾
}

// 出栈
func (this *MyStack) Pop() int {
    // count:队首到倒数第二个元素的个数
    for count := len(this.queue) - 1; count != 0; count-- { // 除了最后一个元素其余元素重新加到队尾
        val := this.queue[0]                 // 取一个队首元素
        this.queue = this.queue[1:]          // 队首后面的元素前移
        this.queue = append(this.queue, val) // 重新加到队尾
    }
    res := this.queue[0]                       // 取队首元素
    this.queue = this.queue[1:len(this.queue)] // 更新队列
    return res
}

// 获取栈顶值
func (this *MyStack) Top() int {
    res := this.Pop()                    // 栈顶出栈
    this.queue = append(this.queue, res) // 重新加到队尾
    return res
}

// 判栈空
func (this *MyStack) Empty() bool {
    return len(this.queue) == 0
}
  • 时间复杂度: pop为O(n),其他为O(1)
  • 空间复杂度: O(n)

有效的括号

20. 有效的括号 - 力扣(LeetCode)

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

遍历字符串,遇到左括号加入栈,遇到右括号就弹出栈顶元素(左括号),若不匹配,则返回false,遍历结束后,若栈内还剩左括号,返回false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' { // 遍历到左括号
            stack = append(stack, v) // 入栈
        } else { // 遍历到右括号
            if len(stack) <= 0 { // 没有左括号
                return false
            }
            if v == ')' && stack[len(stack)-1] != '(' { // 左括号不匹配
                return false
            } else if v == ']' && stack[len(stack)-1] != '[' { // 左括号不匹配
                return false
            } else if v == '}' && stack[len(stack)-1] != '{' { // 左括号不匹配
                return false
            }
            stack = stack[:len(stack)-1] // 出栈
        }
    }
    if len(stack) > 0 { // 还剩左括号未匹配
        return false
    }
    return true
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

优化代码:哈希表,返回判断结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func isValid(s string) bool {
    hash := map[rune]rune{')': '(', ']': '[', '}': '{'}
    stack := make([]rune, 0)
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' { // 遍历到左括号
            stack = append(stack, v) // 入栈
        } else if len(stack) > 0 && stack[len(stack)-1] == hash[v] { // 遍历到右括号栈非空且匹配成功
            stack = stack[:len(stack)-1] // 出栈
        } else { // 遍历到右括号栈空或匹配不成功
            return false
        }
    }
    return len(stack) == 0
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

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

1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。在 S 上反复执行重复项删除操作,直到无法继续删除。

遍历字符串,若栈为空或与栈顶元素不同,则入栈,若与栈顶元素不同,则栈顶元素出栈,遍历结束后,将栈中元素拼接为字符串返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func removeDuplicates(s string) string {
    stack := make([]rune, 0)
    for _, v := range s {
        if len(stack) == 0 || stack[len(stack)-1] != v { // 栈为空或与栈顶元素不同
            stack = append(stack, v) // 入栈
        } else { // 栈非空且与栈顶元素相同
            stack = stack[:len(stack)-1] // 出栈
        }
    }
    return string(stack)
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣(LeetCode)

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*''/'
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

遍历给定字符串,遇到运算符就将栈顶两个元素取出用该运算符处理,结果再入栈,遍历结束返回栈中的运算结果

注意:除法中栈顶元素是除数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func evalRPN(tokens []string) int {
    stack := make([]int, 0)
    for _, v := range tokens {
        if v == "+" { // 遍历到运算符
            val := stack[len(stack)-2] + stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "-" { // 遍历到运算符
            val := stack[len(stack)-2] - stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "*" { // 遍历到运算符
            val := stack[len(stack)-2] * stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "/" { // 遍历到运算符
            val := stack[len(stack)-2] / stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else { // 遇到数字
            val, _ := strconv.Atoi(v)
            stack = append(stack, val) // 入栈
        }
    }
    return stack[0]
}
  • 时间复杂度:O(n)
  • 空间复杂发:O(n)

压缩代码:swich

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func evalRPN(tokens []string) int {
    stack := make([]int, 0)
    for _, v := range tokens {
        val, err := strconv.Atoi(v) // 转为数字
        if err == nil {             // 说明是数字
            stack = append(stack, val) // 数字入栈
        } else { // 说明是运算符
            switch v {
                case "+": stack[len(stack)-2] = stack[len(stack)-2] + stack[len(stack)-1] // 运算结果入栈
                case "-": stack[len(stack)-2] = stack[len(stack)-2] - stack[len(stack)-1] // 运算结果入栈
                case "*": stack[len(stack)-2] = stack[len(stack)-2] * stack[len(stack)-1] // 运算结果入栈
                case "/": stack[len(stack)-2] = stack[len(stack)-2] / stack[len(stack)-1] // 运算结果入栈
            }
            stack = stack[:len(stack)-1] // 更新栈
        }
    }
    return stack[0]
}
  • 时间复杂度:O(n)
  • 空间复杂发:O(n)

滑动窗口最大值

239. 滑动窗口最大值 - 力扣(LeetCode)

给定一个数组和整数k,用k作为滑动窗口大小,窗口从最左侧移动到最右侧,每次移动一位,返回每次窗口移动后的最大值

单调队列:队首出队,队尾入队,队内元素单调;

  1. pop(value):若窗口移除的元素等于单调队列的队首元素,则队列弹出元素,否则不用任何操作
  2. push(value):若push的元素大于队尾元素,则弹出队尾元素,直到push的元素小于等于队尾元素或队空

保持如上规则,每次窗口移动的时候,只要取队首即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
type MyQueue struct {
    queue []int
}

func Constructor() *MyQueue {
    return &MyQueue{
        queue: make([]int, 0),
    }
}

// 获取队首元素
func (m *MyQueue) Front() int {
    return m.queue[0]
}

// 获取队尾元素
func (m *MyQueue) Back() int {
    return m.queue[len(m.queue)-1]
}

// 判队空
func (m *MyQueue) Empty() bool {
    return len(m.queue) == 0
}

// 入队
func (m *MyQueue) Push(val int) {
    for !m.Empty() && val > m.Back() { // 队非空且入队元素大于队尾元素
        m.queue = m.queue[:len(m.queue)-1] // 弹出队尾元素
    }
    m.queue = append(m.queue, val) // 入队尾
}

// 出队
func (m *MyQueue) Pop(val int) {
    if !m.Empty() && val == m.Front() { // 队非空且出队元素等于队首元素
        m.queue = m.queue[1:] // 队首出队
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    queue := Constructor()
    res := make([]int, 0)
    for i := 0; i < k; i++ { // 前k个元素入队
        queue.Push(nums[i]) // 入队
    }
    res = append(res, queue.Front()) // 记录前k个元素的最大值
    for i := k; i < len(nums); i++ { // 遍历数组   
        queue.Pop(nums[i-k]) // 滑动窗口移除最前面的元素
        queue.Push(nums[i]) // 滑动窗口添加最后面的元素
        res = append(res, queue.Front()) // 记录最大值
    }
    return res
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(k)

前 K 个高频元素

347. 前 K 个高频元素 - 力扣(LeetCode)

给定一个数组和一个整数 k ,返回数组中出现频率前 k 高的元素

先统计频率,再对频率排序;统计元素出现的频率可以用map;对频率进行排序,可以用快排和堆

快排

用map统计完频率后,收集不重复的元素,利用字典值对不重复的元素排序,最后返回前k个不重复的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    mp := make(map[int]int)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    for key := range mp { // 遍历字典key
        res = append(res, key) // 记录不重复的元素
    }
    sort.Slice(res, func(a, b int) bool {
        return mp[res[a]] > mp[res[b]] // 降序
    })
    return res[:k]
}
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)

用map统计完频率后,构建小顶堆

是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果是父结点大于等于左右孩子那就是大顶堆,小于等于左右孩子就是小顶堆。大顶堆(堆头是最大元素),小顶堆(堆头是最小元素),用小顶堆每次将最小的元素弹出,最后小顶堆里积累的就是前k个最大元素

更深理解

  • 之所以将交换、比较等操作分离出来,是因为增删切片元素需要传递切片地址,操作切片指针时,无法用索引下标访问数组元素
  • Go语言中函数参数的传递方式都是值传递
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
type Heap [][2]int // 二维表示元素及其频率

// 交换两个节点 
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

// 比较两个节点
func (h Heap) less(i, j int) bool {
    return h[i][1] < h[j][1] // 比较频率 如果实现的是大顶堆,修改这里的判断即可
}

// 节点向上比较交换
func (h Heap) up(i int) {
    for {
        f := (i - 1) / 2            // 父节点在数组中的位置
        if i == f || h.less(f, i) { // 当前节点为根节点或父节点小于当前节点
            break
        }
        h.swap(f, i) // 交换当前节点和父节点的值
        i = f        // 更新当前节点索引继续向上比较
    }
}

// 注意go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x [2]int) {
    *h = append(*h, x) // 加入末尾
    h.up(len(*h) - 1)  // 向上比较交换
}

// 节点向下比较交换
func (h Heap) down(i int) {
    for {
        l := 2*i + 1     // 左孩子
        r := 2*i + 2     // 右孩子
        if l >= len(h) { // 当前节点已经是叶子节点
            break
        }
        minChild := l                   // 默认左孩子值小于右孩子值
        if r < len(h) && h.less(r, l) { // 右孩子存在且小于左孩子
            minChild = r // 更新当前节点的最小子节点
        }
        if h.less(i, minChild) { // 当前节点小于最小子节点
            break
        }
        h.swap(i, minChild) // 交换当前节点和最小子节点位置
        i = minChild        // 更新当前节点索引继续向下比较
    }
}

// 删除堆中位置为i的节点 返回被删节点的值
func (h *Heap) Remove(i int) ([2]int, bool) {
    if i < 0 || i > len(*h)-1 { // 索引越界
        return [2]int{0, 0}, false
    }
    n := len(*h) - 1 // 最后一个节点的索引
    h.swap(i, n)     // 交换要被删除节点和最后的节点
    x := (*h)[n]     // 保存最后节点值
    *h = (*h)[0:n]   // 删除最后节点
    h.down(i)        // 被交换的当前节点向下比较交换
    return x, true
}

// 弹出堆顶的元素,并返回其值
func (h *Heap) Pop() [2]int {
    x, _ := h.Remove(0)
    return x
}

// 根据传入的切片建堆
func BuildHeap(arr [][2]int) Heap {
    h := Heap(arr)                       // 获取给定切片
    for i := len(h)/2 - 1; i >= 0; i-- { // 从堆中末尾节点的父节点到根节点
        h.down(i) // 向下比较交换
    }
    return h
}

func topKFrequent(nums []int, k int) []int {
    mp := map[int]int{}
    res := make([]int, 0)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    h := BuildHeap([][2]int{})   // 初始化堆
    for key, value := range mp { // 遍历字典
        h.Push([2]int{key, value}) // 元素入堆
        if len(h) > k {            // 堆的节点数超过k个
            h.Pop() // 删除顶点(min)
        }
    }
    for i := 0; i < k; i++ { // 遍历堆
        res = append(res, h.Pop()[0])
    }
    return res
}
  • 时间复杂度: O(nlogk)
  • 空间复杂度: O(n)

使用go中标准库提供的heap,需要先实现两个接口定义的五个方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
type Heap [][2]int // 二维表示元素及其频率

func (h Heap) Len() int {
    return len(h)
}

// 比较两个节点
func (h Heap) Less(i, j int) bool {
    return h[i][1] < h[j][1] // 按照频率排序节点
}

// 交换两个节点
func (h Heap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

// go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x interface{}) {
    *h = append(*h, x.([2]int)) // 向末尾添加节点
}

// 删除节点
func (h *Heap) Pop() interface{} {
    old := *h         // 保存当前根
    n := len(old)     // 节点数
    x := old[n-1]     // 保存最后一个节点
    *h = old[0 : n-1] // 删除最后一个节点
    return x          // 返回删除的节点
}

func topKFrequent(nums []int, k int) []int {
    mp := map[int]int{}
    res := make([]int, k)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    h := &Heap{}                 // 初始化堆
    heap.Init(h)                 // 用go标准库提供的heap
    for key, value := range mp { // 遍历字典
        heap.Push(h, [2]int{key, value}) // 元素入堆
        if h.Len() > k {                 // 堆的节点数超过k个
            heap.Pop(h) // 删除顶点(min)
        }
    }
    for i := 0; i < k; i++ { // 遍历堆
        res[k-i-1] = heap.Pop(h).([2]int)[0] // 将堆中排序后的元素加入结果集
    }
    return res
}

自己实现小顶堆

  • 借助 哈希表 来建立数字和其出现次数的映射,遍历一遍数组统计元素的频率
  • 维护一个元素数目为 k 的最小堆
  • 每次都将新的元素与堆顶元素(堆中频率最小的元素)进行比较
  • 如果新的元素的频率比堆顶端的元素大,则弹出堆顶端的元素,将新的元素添加进堆中
  • 最终,堆中的 k 个元素即为前 k 个高频元素
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    // 统计各元素频率
    mp := make(map[int]int)
    for _, v := range nums {
        mp[v]++
    }
    // 维护一个大小为k的最小堆
    // 每个节点表示为元素及其频率
    heap := make([][2]int, 0)
    // 遍历字典元素入堆
    for key, v := range mp {
        // 判当前堆大小是否大于k
        if len(heap) >= k {
            // 判当前元素是否小于堆顶元素
            if v < heap[0][1] {
                // 当前元素无需入堆
                continue
            } else {
                // 修改堆顶元素为当前元素
                heap[0] = [2]int{key, v}
            }
        } else {
            // 当前元素入堆
            heap = append(heap, [2]int{key, v})
        }
        // 堆化,从尾节点遍历到根节点,维护小顶堆性质
        for i := len(heap)/2 - 1; i >= 0; i-- {
            heapify(heap, len(heap), i)
        }
    }
    // 小顶堆排序为降序
    for i := len(heap) - 1; i >= 0; i-- {
        // 交换堆顶元素和未排定的末尾元素
        heap[0], heap[i] = heap[i], heap[0]
        // 将未排定元素从堆顶向下重新堆化
        heapify(heap, i, 0)
    }
    // 将堆中元素全部放入结果集
    for _, v := range heap {
        res = append(res, v[0])
    }
    return res
}
func heapify(heap [][2]int, len, curIdx int) {
    // 初始化最小元素索引为当前元素索引
    minIdx := curIdx
    // 求得当前元素左右孩子索引
    l := 2*curIdx + 1
    r := 2*curIdx + 2
    // 判左右孩子是否小于当前最小元素
    if l < len && heap[l][1] < heap[minIdx][1] {
        minIdx = l
    }
    if r < len && heap[r][1] < heap[minIdx][1] {
        minIdx = r
    }
    if minIdx != curIdx {
        // 交换当前元素与最小元素
        heap[curIdx], heap[minIdx] = heap[minIdx], heap[curIdx]
        // 向下递归
        heapify(heap, len, minIdx)
    }
}

桶排序

依旧使用哈希表统计频率,统计完成后,创建一个数组,将频率作为数组下标,对于出现频率不同的数字集合,存入对应的数组下标即可

由于k不会大于数组长度且最大频率可能为len(nums),所以定义len(nums)+1个桶,每个桶中存相同频率的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    // 统计各元素频率
    mp := make(map[int]int)
    for _, v := range nums {
        mp[v]++
    }
    // 初始化len(nums)+1个桶
    // 每个桶中存相同频率的元素
    buckets := make([][]int, len(nums)+1)
    // 遍历字典元素入对应桶
    for key, v := range mp {
        // 判该频率的桶是否为空
        if len(buckets[v]) == 0 {
            // 初始化该频率的桶
            buckets[v] = make([]int, 0)
        }
        // 按频率将元素放入对应桶
        buckets[v] = append(buckets[v], key)
    }
    // 倒序遍历桶取k个元素
    for i := len(buckets) - 1; i >= 0; i-- {
        // 判该桶是否非空
        if len(buckets[i]) != 0 {
            // 遍历该桶
            for _, v := range buckets[i] {
                // 桶中当前元素加入结果集
                res = append(res, v)
                // 更新k
                k--
                // 判是否取够k个元素
                if k == 0 {
                    return res
                }
            }
        }
    }
    return res
}

附加

最小栈

155. 最小栈 - 力扣(LeetCode)

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈

思路一:维护一个整型量保存最小值,在push和pop时更新最小值属性,若pop了最小值,则要遍历栈更新最小值(不推荐)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
type MinStack struct {
    minVal int
    stack  []int
}

func Constructor() MinStack {
    return MinStack{
        minVal: math.MaxInt, 
        stack: make([]int, 0)}
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    if val < this.minVal {
        this.minVal = val
    }
}

func (this *MinStack) Pop() {
    if this.Top() == this.minVal {
        this.minVal = math.MaxInt
        for i := 0; i < len(this.stack)-1; i++ {
            if this.stack[i] < this.minVal {
                this.minVal = this.stack[i]
            }
        }
    }
    this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minVal
}

思路二:维护一个最小栈,保证栈顶一定是最小值,若push元素大于最小值,则向最小栈push最小值,pop正常。保证每次pushpop后最小栈顶一定最小

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type MinStack struct {
    min   []int
    stack []int
}

func Constructor() MinStack {
    return MinStack{
        min:   make([]int, 0),
        stack: make([]int, 0)}
}

func (this *MinStack) Push(val int) {
    minVal := this.GetMin()
    if val < minVal {
        this.min = append(this.min, val)
    } else {
        this.min = append(this.min, minVal)
    }
    this.stack = append(this.stack, val)
}

func (this *MinStack) Pop() {
    this.min = this.min[:len(this.min)-1]
    this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    if len(this.min) != 0 {
        return this.min[len(this.min)-1]
    }
    return 1 << 31 // 最小整型值
}

字符串解码

394. 字符串解码 - 力扣(LeetCode)

给定一个字符串,将括号里的字符重复括号前数字的次数,最终返回一个字符串

思路:遍历字符串入栈,遇到右括号时,不断弹栈,保存括号里的字符和括号前的数字,将括号里字符重复入栈给定次数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
func decodeString(s string) string {
    stack := make([]rune, 0)
    for _, v := range s {
        // 解码
        if v == ']' {
            temp := make([]rune, 0)
            // 逆序取出括号中的字符串
            for stack[len(stack)-1] != '[' {
                temp = append(temp, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 弹出'['
            stack = stack[:len(stack)-1]
            // 保存重复次数(rune -> int)
            countSlice := make([]rune, 0)
            // 逆序取出数字
            for len(stack) != 0 && stack[len(stack)-1] <= '9' && stack[len(stack)-1] >= '0' {
                countSlice = append(countSlice, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 翻转
            for i, j := 0, len(countSlice)-1; i < j; i, j = i+1, j-1 {
                countSlice[i], countSlice[j] = countSlice[j], countSlice[i]
            }
            count, _ := strconv.Atoi(string(countSlice))
            // 重复字符入栈
            for range count {
                // 逆序遍历括号中字符
                for i := len(temp) - 1; i >= 0; i-- {
                    stack = append(stack, temp[i])
                }
            }
        } else {
            stack = append(stack, v)
        }
    }
    return string(stack)
}
// 写法二:用slices.Reverse翻转 直接追加打散的切片元素
func decodeString(s string) string {
    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == ']' {
            // 取出逆序字符串
            inter := make([]byte, 0)
            for len(stack) != 0 && stack[len(stack)-1] != '[' {
                inter = append(inter, stack[len(stack)-1])
                stack = stack[:len(stack)-1]

            }
            // 弹出]
            stack = stack[:len(stack)-1]
            // 取出逆序数字
            countByte := make([]byte, 0)
            for len(stack) != 0 && stack[len(stack)-1] >= '0' && stack[len(stack)-1] <= '9' {
                countByte = append(countByte, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 翻转逆序
            slices.Reverse(countByte)
            slices.Reverse(inter)
            count, _ := strconv.Atoi(string(countByte))
            // 解码字符串入栈
            for j := 0; j < count; j++ {
                stack = append(stack, inter...)
            }
        } else {
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

克隆图

133. 克隆图 - 力扣(LeetCode)

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)

思路一:非递归,用栈实现(不推荐)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
func cloneGraph(node *Node) *Node {
    if node == nil {
        return node
    }
    stack := make([]*Node, 0)
    newStack := make([]*Node, 0)
    mp := make(map[int]*Node)
    temp := make(map[int]bool)
    // 给定节点入栈
    stack = append(stack, node)
    temp[node.Val] = true
    // 遍历所有旧节点创建对应新节点
    for len(stack) != 0 {
        // 取出一个节点作为当前节点
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 将当前节点的邻居节点入栈
        for _, v := range cur.Neighbors {
            // 未遍历过该节点
            if !temp[v.Val] {
                stack = append(stack, v)
                temp[v.Val] = true
            }
        }
        // 构造当前节点的拷贝
        newNode := &Node{
            Val:       cur.Val,
            Neighbors: cur.Neighbors,
        }
        // 将新节点存入字典
        mp[newNode.Val] = newNode
        // 将新节点存入新栈
        newStack = append(newStack, newNode)
    }
    for len(newStack) != 0 {
        // 取出一个节点作为当前节点
        cur := newStack[len(newStack)-1]
        newStack = newStack[:len(newStack)-1]
        // 保存当前节点的新邻居节点
        temp := make([]*Node, 0)
        // 遍历当前节点的邻居节点
        for i := 0; i < len(cur.Neighbors); i++ {
            // 在字典中找到对应的新节点
            if v, ok := mp[cur.Neighbors[i].Val]; ok {
                // 保存当前节点的新邻居节点
                temp = append(temp, v)
            }
        }
        // 修改所有邻居节点为新节点
        cur.Neighbors = nil
        cur.Neighbors = append(cur.Neighbors, temp...)
    }
    // 字典中找给定节点对应的新节点
    if v, ok := mp[node.Val]; ok {
        return v
    }
    return nil
}

思路二:递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func cloneGraph(node *Node) *Node {
    // 记录旧->新节点的对应
    mp := make(map[*Node]*Node)
    return clone(node, mp)
}
func clone(cur *Node, mp map[*Node]*Node) *Node {
    if cur == nil {
        return cur
    }
    // 字典中存在该节点对应的新节点
    if v, ok := mp[cur]; ok {
        return v
    }
    // 构建新节点
    newNode := &Node{
        Val: cur.Val,
        Neighbors: make([]*Node, len(cur.Neighbors)),
    }
    // 更新字典:旧节点->新节点
    mp[cur] = newNode
    // 遍历当前节点的邻居节点
    for i := 0; i < len(cur.Neighbors); i++ {
        newNode.Neighbors[i] = clone(cur.Neighbors[i], mp)
    }
    return newNode
}

01 矩阵

542. 01 矩阵 - 力扣(LeetCode)

思路一:对每个元素BFS(超时)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
func updateMatrix(mat [][]int) [][]int {
    // 遍历给定矩阵
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[0]); j++ {
            // 遇到元素1
            if mat[i][j] == 1 {
                queue := make([][2]int, 0)
                // 当前元素入队
                queue = append(queue, [2]int{i, j})
                // 记录距离
                dist := 0
                // 标记是否找到最近元素0
                isFind := false
                // 标记该坐标是否被遍历过
                mp := make(map[[2]int]bool)
                // BFS
                for len(queue) != 0 && !isFind {
                    // 记录本层元素数
                    count := len(queue)
                    // 遍历本层所有元素
                    for k := 0; k < count && !isFind; k++ {
                        // 记录队首元素后出队
                        curI, curJ := queue[0][0], queue[0][1]
                        queue = queue[1:]
                        // 标记当前元素已遍历过
                        mp[[2]int{curI, curJ}] = true
                        // 找到元素0
                        if mat[curI][curJ] == 0 {
                            // 修改矩阵对应元素为距离
                            mat[i][j] = dist
                            // 标记找到最近元素0
                            isFind = true
                        }
                        // 上方元素入队
                        if curI != 0 && !mp[[2]int{curI - 1, curJ}] {
                            queue = append(queue, [2]int{curI - 1, curJ})
                        }
                        // 下方元素入队
                        if curI != len(mat)-1 && !mp[[2]int{curI + 1, curJ}] {
                            queue = append(queue, [2]int{curI + 1, curJ})
                        }
                        // 左方元素入队
                        if curJ != 0 && !mp[[2]int{curI, curJ - 1}] {
                            queue = append(queue, [2]int{curI, curJ - 1})
                        }
                        // 右方元素入队
                        if curJ != len(mat[0])-1 && !mp[[2]int{curI, curJ + 1}] {
                            queue = append(queue, [2]int{curI, curJ + 1})
                        }
                    }
                    // 距离+1
                    dist++
                }
            }
        }
    }
    return mat
}

思路二BFS:更新每个元素0四周需要更新的元素,再更新每个更新过的元素四周需要更新的元素,每次都更新完一级四周需要更新的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func updateMatrix(mat [][]int) [][]int {
    queue := make([][2]int, 0)
    // 遍历给定矩阵
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[0]); j++ {
            // 遇到元素0
            if mat[i][j] == 0 {
                // 坐标入队
                queue = append(queue, [2]int{i, j})
            } else {
                // 标记当前元素需要更新
                mat[i][j] = -1
            }
        }
    }
    // 设置四周偏移量
    ds := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    // 遍历队列
    for len(queue) != 0 {
        // 保存队首后出队
        x, y := queue[0][0], queue[0][1]
        queue = queue[1:]
        // 遍历当前元素的四周
        for _, offset := range ds {
            // 给当前元素下标设置偏移量
            curX := x + offset[0]
            curY := y + offset[1]
            // 坐标有效且对应元素需要更新
            if curX >= 0 && curY >= 0 && curX < len(mat) && curY < len(mat[0]) && mat[curX][curY] == -1 {
                // 更新元素值
                mat[curX][curY] = mat[x][y] + 1
                // 更新后元素的下标入队
                queue = append(queue, [2]int{curX, curY})
            }
        }
    }
    return mat
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

数据流的中位数

295. 数据流的中位数 - 力扣(LeetCode)

使用两个优先队列(堆)来维护整个数据流数据,为了可以在 O(1) 的复杂度内取得当前中位数,令 l 为大根堆,r 为小根堆,并人为固定 lr 之前存在如下关系:

  • 当数据流元素数量为偶数:lr 大小相同,此时中位数为两者堆顶元素的平均值;
  • 当数据流元素数量为奇数:lr 多一,此时中位数为 l 的堆顶原数

当添加一个数 num 时需要分情况讨论:

  1. $num≤max{l}$

    此时 num 小于等于中位数,需要将该数添加到 l 中。新的中位数将小于等于原来的中位数,因此可能需要将 l 中最大的数移动到 r 中。

  2. $num>max{r}$

    此时 num 大于中位数,需要将该数添加到 r 中。新的中位数将大于等于原来的中位数,因此可能需要将 r 中最小的数移动到 l 中。

具体是否移动取决与俩堆的大小,目标是维持俩堆大小相等或左比右大1

特别地,当 l 为空时,将 num 添加到 l

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
type MedianFinder struct {
    heapL Heap // 大顶堆
    heapR Heap // 小顶堆
}

func Constructor() MedianFinder {
    return MedianFinder{
        heapL: Heap{},
        heapR: Heap{},
    }
}

func (this *MedianFinder) AddNum(num int) {
    // 判大顶堆是否为空或加入值小于大顶堆顶
    if len(this.heapL) == 0 || num < this.heapL[0] {
        // 加入大顶堆
        this.heapL.Push(num, 1)
        // 判大顶堆元素是否比小顶堆元素多一个以上
        if len(this.heapL)-len(this.heapR) > 1 {
            // 大顶堆顶移至小顶堆
            this.heapR.Push(this.heapL.Pop(1), 0)
        }
    } else {
        // 加入小顶堆
        this.heapR.Push(num, 0)
        // 判小顶堆元素是否多于大顶堆
        if len(this.heapR) > len(this.heapL) {
            // 小顶堆顶移至大顶堆
            this.heapL.Push(this.heapR.Pop(0), 1)
        }
    }
}

func (this *MedianFinder) FindMedian() float64 {
    // 判大顶堆元素是否多于小顶堆
    if len(this.heapL) > len(this.heapR) {
        return float64(this.heapL[0])
    } else {
        return float64(this.heapL[0]+this.heapR[0]) / 2.0
    }
}

type Heap []int

func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j, sign int) bool {
    if sign == 0 {
        // 小顶堆
        return h[i] < h[j]
    } else {
        // 大顶堆
        return h[i] > h[j]
    }
}

func (h Heap) up(i, sign int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father, sign) {
        h.swap(father, i)
        h.up(father, sign)
    }
}

func (h Heap) down(i, sign int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, largest, sign) {
        largest = left
    }
    if right < len(h) && h.less(right, largest, sign) {
        largest = right
    }
    if largest != i {
        h.swap(largest, i)
        h.down(largest, sign)
    }
}

func (h *Heap) Push(x, sign int) {
    *h = append(*h, x)
    h.up(len(*h)-1, sign)
}

func (h *Heap) Remove(i, sign int) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    h.swap(i, len(*h)-1)
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    if i < len(*h) {
        father := (i - 1) / 2
        if father >= 0 && h.less(i, father, sign) {
            h.up(i, sign)
        } else {
            h.down(i, sign)
        }
    }
    return x, true
}

func (h *Heap) Pop(sign int) int {
    x, _ := h.Remove(0, sign)
    return x
}
  • 时间复杂度:
    • addNum: O(logn),其中 n 为累计添加的数的数量
    • findMedian: O(1)。
  • 空间复杂度:O(n),主要为堆的开销

简化路径

71. 简化路径 - 力扣(LeetCode)

给定一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),要求将其转化为 更加简洁的规范路径

在 Unix 风格的文件系统中规则如下:

  • 一个点 '.' 表示当前目录本身。
  • 此外,两个点 '..' 表示将目录切换到上一级(指向父目录)。
  • 任意多个连续的斜杠(即,'//''///')都被视为单个斜杠 '/'
  • 任何其他格式的点(例如,'...''....')均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式:

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/'
  • 最后一个目录名(如果存在)不能'/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.''..')。

返回简化后得到的 规范路径

思路:栈内只存有效文件/目录名,最后对栈内各元素加分隔符

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 写法一:手动分割
func simplifyPath(path string) string {
    // 栈内存各个有效文件/目录名称
    stack := make([]string, 0)
    i := 0
    for i < len(path) {
        // 判是否遇到.
        if path[i] == '.' {
            // 遍历该连续.
            cnt := 0
            for i < len(path) && path[i] == '.' {
                i++
                cnt++
            } // 此时i指向不为.
            // 判是否为.开头的文件/目录名称
            if i < len(path) && path[i] != '/' {
                start := i
                // 遍历该有效字符
                for i < len(path) && path[i] != '/' {
                    i++
                } // 此时i指向/
                stack = append(stack, path[start-cnt:i])
            } else if cnt == 1 { // 处理.
                continue
            } else if len(stack) != 0 && cnt == 2 {
                stack = stack[:len(stack)-1]
            } else if cnt >= 3 {
                stack = append(stack, path[i-cnt:i])
            }
        } else if path[i] == '/' {
            for i < len(path) && path[i] == '/' {
                i++
            } // 此时i指向不为/
        } else { // 此时i指向有效字符且非.
            start := i
            // 遍历该有效字符
            for i < len(path) && path[i] != '/' {
                i++
            } // 此时i指向/
            stack = append(stack, path[start:i])
        }
    }
    // 将各有效文件/目录用分隔符'/'连接
    res := strings.Join(stack, "/")
    // 路径首加/
    res = "/" + res
    return res
}
// 写法二:调库函数分割
func simplifyPath(path string) string {
    // 栈内存储有效文件/目录名称
    stack := []string{}
    // 遍历按分隔符'/'切割后的字符串切片
    for _, v := range strings.Split(path, "/") {
        if v == ".." {
            if len(stack) != 0 {
                stack = stack[:len(stack)-1]
            }
        } else if v != "." && v != "" {
            stack = append(stack, v)
        }
    }
    res := "/" + strings.Join(stack, "/")
    return res
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

基本计算器

224. 基本计算器 - 力扣(LeetCode)

给定一个字符串表达式 s ,实现一个基本计算器来计算并返回它的值。

思路:使用两个栈 nums 和 ops

  • nums : 存放所有的数字

  • ops :存放加、减、左括号

从前往后对遍历到的字符分情况处理:

  • 空格 : 跳过
  • ( : 直接加入 ops 中,等待与之匹配的 )
  • 数字 : 从当前位置开始继续往后取,将整一个连续数字整体取出,加入 nums
  • ) : 使用现有的 numsops 进行计算,直到ops为空或遇到左括号,计算结果放到 numsops中该左括号出栈
  • +/- : 使用现有的 numsops 进行计算,直到ops为空或遇到左括号,计算结果放到 nums,最后+/-入栈,;若为(-,则加0后再入栈

注意:

  • 由于第一个数可能是负数,为了减少边界判断。一个小技巧是先往 nums 添加一个 0

  • 为防止 () 内出现的首个字符为运算符,将所有的空格去掉,并将 (- 替换为 (0-(+ 替换为 (0+(当然也可以不进行这样的预处理,将这个处理逻辑放到循环里去做)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func calculate(s string) int {
    // 清除字符串s中所有空格
    s = strings.ReplaceAll(s, " ", "")
    // nums中预加0防止一开始为-
    nums, ops := []int{0}, []byte{}
    // 利用nums和ops计算
    cal := func() {
        op := ops[len(ops)-1]
        ops = ops[:len(ops)-1]
        if op == '+' {
            nums[len(nums)-2] += nums[len(nums)-1]
        } else {
            nums[len(nums)-2] -= nums[len(nums)-1]
        }
        nums = nums[:len(nums)-1]
    }
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            continue
        } else if s[i] == '(' {
            ops = append(ops, '(')
        } else if s[i] <= '9' && s[i] >= '0' {
            // 将整一个连续数字整体取出
            start := i
            for i < len(s) && s[i] >= '0' && s[i] <= '9' {
                i++
            }
            num, _ := strconv.Atoi(s[start:i])
            nums = append(nums, num)
            i--
        } else { // + - )
            // 处理ops中+/-
            for len(ops) != 0 && ops[len(ops)-1] != '(' {
                cal()
            }
            if s[i] == ')' {
                // (出栈
                ops = ops[:len(ops)-1]
            } else { // +/-
                // 判字符串中是否为(-或(+
                if i != 0 && s[i-1] == '(' {
                    // 加0变(0-或(0+
                    nums = append(nums, 0)
                }
                ops = append(ops, s[i])
            }
        }
    }
    if len(ops) != 0 {
        cal()
    }
    return nums[len(nums)-1]
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

从字符串中移除星号

2390. 从字符串中移除星号 - 力扣(LeetCode)

给定一个包含若干星号 * 的字符串 s 。移除星号及其 左侧 最近的那个 非星号 字符,返回移除 所有 星号之后的字符串

思路:栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func removeStars(s string) string {
    stack := make([]byte, 0)
    for _, ch := range s {
        if ch == '*' {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, byte(ch))
        }
    }
    return string(stack)
}

小行星碰撞

735. 小行星碰撞 - 力扣(LeetCode)

给定一个整数数组 asteroids,表示在同一行的小行星。

对于数组中的每一个元素,其绝对值表示小行星的大小,正负表示小行星的移动方向(正表示向右移动,负表示向左移动)。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则:两个小行星相互碰撞,较小的小行星会爆炸。如果两颗小行星大小相同,则两颗小行星都会爆炸。两颗移动方向相同的小行星,永远不会发生碰撞。

思路:栈

注意:只有当前元素为负(向左)与栈顶元素为正(向右)才会碰撞,当前元素为正(向右)栈顶元素为负(向左)不会碰撞

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func asteroidCollision(asteroids []int) []int {
    stack := make([]int, 0)
    for _, cur := range asteroids {
        // 标记当前元素是否存在
        curAlive := true
        // 不断循环直至当前元素爆炸或栈空或当前元素与栈顶不碰撞
        for curAlive && len(stack) != 0 && cur < 0 && stack[len(stack)-1] > 0 {
            // 判当前元素是否存在
            curAlive = -cur > stack[len(stack)-1]
            // 判栈顶元素是否爆炸
            if stack[len(stack)-1] <= -cur {
                stack = stack[:len(stack)-1]
            }
        }
        if curAlive {
            stack = append(stack, cur)
        }
    }
    return stack
}

最近的请求次数

933. 最近的请求次数 - 力扣(LeetCode)

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类:

  • RecentCounter() 初始化计数器,请求数为 0 。
  • int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t

思路:队列

由于每次收到的请求的时间都比之前的大,因此从队首到队尾的时间值是单调递增的。当在时间 t 收到请求时,为了求出 [t−3000,t] 内发生的请求数,不断从队首弹出早于 t−3000 的时间。循环结束后队列的长度就是 [t−3000,t] 内发生的请求数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
type RecentCounter struct {
    queue []int
}

func Constructor() RecentCounter {
    return RecentCounter{}
}

func (this *RecentCounter) Ping(t int) int {
    // 过期的时间出队
    for len(this.queue) > 0 && this.queue[0] < t-3000 {
        this.queue = this.queue[1:]
    }
    // 当前时间入队
    this.queue = append(this.queue, t)
    // 返回当前队长(都有效)
    return len(this.queue)
}

Dota2 参议院

给定一个字符串,其中只包含RD两种字符,分别代表两个阵营的参议院,每轮中每个议员可以禁止另一议员的权利或宣布胜利,失去权利的议员将在过程中被跳过,若议员发现有权利投票的议员都是 同一个阵营的 ,则可以该阵营宣布胜利,返回胜利的阵营输出,应该是 "Radiant""Dire"

思路:贪心 + 循环队列

  1. 创建两个队列,遍历一遍字符串,按照投票顺序(下标)分别存储R方和D方每一名议员(下标)
  2. 逐个比较队首,值小的说明先投,另一个队首出队(ban),值小的从队首出队加上字符串长度后(代表是下一轮)加入队尾
  3. 当一方队列为空,另一方获胜

注意:值小的从队首出队加上字符串长度,可以保证这个议员只会参加下一轮,或者被上一轮的对手干掉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func predictPartyVictory(senate string) string {
    rQueue, dQueue := []int{}, []int{}
    for i, ch := range senate {
        if ch == 'R' {
            rQueue = append(rQueue, i)
        } else {
            dQueue = append(dQueue, i)
        }
    }
    for len(rQueue) != 0 && len(dQueue) != 0 {
        if rQueue[0] < dQueue[0] {
            rQueue = append(rQueue, rQueue[0]+len(senate))
        } else {
            dQueue = append(dQueue, dQueue[0]+len(senate))
        }
        rQueue = rQueue[1:]
        dQueue = dQueue[1:]
    }
    if len(rQueue) == 0 {
        return "Dire"
    }
    return "Radiant"
}
Built with Hugo
Theme Stack designed by Jimmy