队列专题

迈莫coding

共 10073字,需浏览 21分钟

 ·

2024-03-24 10:00

 

 

232.用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

 

  • 题目描述

使用栈实现队列的下列操作:

push(x) -- 将一个元素放入队列的尾部。

pop() -- 从队列首部移除元素。

peek() -- 返回队列首部的元素。

empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

 

  • 实现思想

    • 定义两个栈,栈A和栈B,栈A负责接收数据,栈B负责出数据,如果出数据时,栈B为空,那么将栈A中的数据写入栈B中,再出数据。

  • 代码实现

 

type MyQueue struct {
stackA []int
stackB []int
}


func Constructor() MyQueue {
return MyQueue{
stackA : make([]int, 0),
stackB : make([]int, 0),
}
}


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


func (this *MyQueue) Pop() int {
if len(this.stackB) == 0 {
for len(this.stackA) != 0 {
pop := this.stackA[len(this.stackA)-1]
this.stackB = append(this.stackB, pop)
this.stackA = this.stackA[:len(this.stackA)-1]
}
}
pop := this.stackB[len(this.stackB)-1]
this.stackB = this.stackB[:len(this.stackB)-1]
return pop
}


func (this *MyQueue) Peek() int {
if len(this.stackB) == 0 {
for len(this.stackA) != 0 {
pop := this.stackA[len(this.stackA)-1]
this.stackB = append(this.stackB, pop)
this.stackA = this.stackA[:len(this.stackA)-1]
}
}
return this.stackB[len(this.stackB)-1]
}


func (this *MyQueue) Empty() bool {
return len(this.stackA) <= 0 && len(this.stackB) <= 0
}


/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/

 

225. 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

 

  • 题目描述

 

使用队列实现栈的下列操作:

  1. push(x) -- 元素 x 入栈

  2. pop() -- 移除栈顶元素

  3. top() -- 获取栈顶元素

  4. empty() -- 返回栈是否为空

注意:

  1. 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

  2. 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

  3. 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

 

  • 实现思想

 

  • 定义两个队列,队列A和队列B,队列A只负责接收数据,队列B真正存储数据,当数据push进来,会先由队列A接收,然后再将队列B中的数据依次写入到队列A中,这样队列A中就是完整数据,队首为最近入队数据,再将队列A和队列B互换。

 

  • 代码实现

 

type MyStack struct {
queueA []int
queueB []int
}


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


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


func (this *MyStack) move() {
if len(this.queueB) == 0 {
this.queueA, this.queueB = this.queueB, this.queueA
}else {
this.queueA = append(this.queueA, this.queueB[0])
this.queueB = this.queueB[1:]
this.move()
}
}


func (this *MyStack) Pop() int {
if len(this.queueB) == 0 {
return 0
}
pop := this.queueB[0]
this.queueB = this.queueB[1:]
return pop
}


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


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


/**
* Your MyStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.Empty();
*/

 

 

20. 有效的括号

https://leetcode.cn/problems/valid-parentheses/

 

  • 题目描述

 

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

  3. 注意空字符串可被认为是有效字符串。

示例 1:

  1. 输入: "()"

  2. 输出: true

示例 2:

  1. 输入: "()[]{}"

  2. 输出: true

示例 3:

  1. 输入: "(]"

  2. 输出: false

示例 4:

  1. 输入: "([)]"

  2. 输出: false

示例 5:

  1. 输入: "{[]}"

  2. 输出: true

 

  • 实现思想

 

  • 栈思想。用一个map保存左括号对应的右边括号,遍历字符串s,如果遇到左边括号,将其对应的右边括号入栈,否则情况下判断栈首与遍历的字符是否相等,若相等继续遍历,若不相等表示括号是无效的,返回false。

 

  • 代码实现

func isValid(s string) bool {
tempMap := map[byte]byte{'(':')', '{':'}', '[':']'}
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] == '(' || s[i] == '{' || s[i] == '[' {
stack = append(stack, tempMap[s[i]])
}else if len(stack) == 0 || stack[len(stack)-1] != s[i] {
return false
}else {
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}

 

 

 

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

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

 

  • 题目描述

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

  1. 输入:"abbaca"

  2. 输出:"ca"

  3. 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

  1. 1 <= S.length <= 20000

  2. S 仅由小写英文字母组成。

 

  • 实现思想

 

  • 栈思想。遍历字符串s,如果栈非空并且栈首不等于遍历值,将该值追加栈中,如果相等话,将栈首移除。

 

  • 代码实现

func removeDuplicates(s string) string {
res := []byte{}
for i := 0; i < len(s); i++ {
if len(res) > 0 && res[len(res)-1] == s[i] {
res = res[:len(res)-1]
}else {
res = append(res, s[i])
}
}
return string(res)
}

 

 

150. 逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

 

  • 题目描述

 

根据 逆波兰表示法,求表达式的值。

有效的运算符包括 + ,  - ,  * ,  / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

  1. 输入: ["2", "1", "+", "3", " * "]

  2. 输出: 9

  3. 解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

  1. 输入: ["4", "13", "5", "/", "+"]

  2. 输出: 6

  3. 解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

  1. 输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]

  2. 输出: 22

解释:该算式转化为常见的中缀算术表达式为:

((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

逆波兰表达式:是一种后缀表达式,所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

  1. 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

 

  • 实现思想

    • 栈思想。

 

  • 代码实现

 

func evalRPN(tokens []string) int {
stack := make([]int, 0)
use := map[string]struct{}{
"+": {},
"-": {},
"*": {},
"/": {},
}
for i := 0; i < len(tokens); i++ {
if _, ok := use[tokens[i]]; ok {
tempFirst := stack[len(stack)-1]
tempSecond := stack[len(stack)-2]
stack = stack[:len(stack)-2]
if tokens[i] == "+" {
stack = append(stack, tempFirst+tempSecond)
} else if tokens[i] == "-" {
stack = append(stack, tempSecond-tempFirst)
} else if tokens[i] == "*" {
stack = append(stack, tempFirst*tempSecond)
} else if tokens[i] == "/" {
stack = append(stack, tempSecond/tempFirst)
}
continue
}
tempInteger, _ := strconv.Atoi(tokens[i])
stack = append(stack, tempInteger)
}
return stack[len(stack)-1]
}

 

239. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

 

  • 题目描述

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶:

你能在线性时间复杂度内解决此题吗?

013a178a8e6e9645b4692058b1286f92.webp

提示:

  1. 1 <= nums.length <= 10^5

  2. -10^4 <= nums[i] <= 10^4

  3. 1 <= k <= nums.length

 

  • 实现思想

 

  • 定一个单调递减队列,用于保存在滑动窗口中递减队列,队首即为窗口中最大值,每次遍历过程中需要判断遍历值和队首是否相等,如果相等则需要将该值移除队列;还需要将遍历值添加到队列中,使得队列中的元素始终是窗口中一次递减的元素。

 

  • 代码实现

 

func maxSlidingWindow(nums []int, k int) []int {
q := &MyQueue {
queue: make([]int, 0),
}
result := make([]int, 0)
for i := 0; i < k; i++ {
q.push(nums[i])
}
result = append(result, q.peek())
for i := k; i < len(nums); i++ {
q.pop(nums[i-k])
q.push(nums[i])
result = append(result, q.peek())
}
return result
}


type MyQueue struct{
queue []int
}


func (this *MyQueue) pop(val int) {
if len(this.queue) > 0 && this.queue[0] == val {
this.queue = this.queue[1:]
}
}


func (this *MyQueue) push(val int) {
for len(this.queue) > 0 && this.queue[len(this.queue)-1] < val {
this.queue = this.queue[:len(this.queue)-1]
}
this.queue = append(this.queue, val)
}


func (this *MyQueue) peek() int {
return this.queue[0]
}

 

 

347.前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/

 

  • 题目描述

 

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

示例 1:

  1. 输入: nums = [1,1,1,2,2,3], k = 2

  2. 输出: [1,2]

示例 2:

  1. 输入: nums = [1], k = 1

  2. 输出: [1]

提示:

  1. 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。

  2. 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。

  3. 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。

  4. 你可以按任意顺序返回答案。

 

  • 实现思想

 

  • 定义一个map用于存储数字出现的次数,然后对map中key值排序,排序顺序为降序,取前K个元素。

 

  • 代码实现

 

func topKFrequent(nums []int, k int) []int {
countMap := make(map[int]int)
result := make([]int, 0)
for i := 0; i < len(nums); i++ {
countMap[nums[i]]++
}
for k, _ :=range countMap {
result = append(result, k)
}
sort.Slice(result, func(a, b int) bool {
return countMap[result[a]] > countMap[result[b]]
})
return result[:k]
}

 

 

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报