隊列專題

 

 

232.用棧實現(xiàn)隊列

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

 

• 題目描述

使用棧實現(xiàn)隊列的下列操作：

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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

• 假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。

 

• 實現(xiàn)思想

  • 定義兩個棧，棧A和棧B，棧A負責(zé)接收數(shù)據(jù)，棧B負責(zé)出數(shù)據(jù)，如果出數(shù)據(jù)時，棧B為空，那么將棧A中的數(shù)據(jù)寫入棧B中，再出數(shù)據(jù)。

• 代碼實現(xiàn)

 

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. 用隊列實現(xiàn)棧

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

 

• 題目描述

 

使用隊列實現(xiàn)棧的下列操作：

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. 你可以假設(shè)所有操作都是有效的（例如, 對一個空的棧不會調(diào)用 pop 或者 top 操作）。

 

• 實現(xiàn)思想

 

• 定義兩個隊列，隊列A和隊列B，隊列A只負責(zé)接收數(shù)據(jù)，隊列B真正存儲數(shù)據(jù)，當(dāng)數(shù)據(jù)push進來，會先由隊列A接收，然后再將隊列B中的數(shù)據(jù)依次寫入到隊列A中，這樣隊列A中就是完整數(shù)據(jù)，隊首為最近入隊數(shù)據(jù)，再將隊列A和隊列B互換。

 

• 代碼實現(xiàn)

 

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

 

• 實現(xiàn)思想

 

• 棧思想。用一個map保存左括號對應(yīng)的右邊括號，遍歷字符串s，如果遇到左邊括號，將其對應(yīng)的右邊括號入棧，否則情況下判斷棧首與遍歷的字符是否相等，若相等繼續(xù)遍歷，若不相等表示括號是無效的，返回false。

 

• 代碼實現(xiàn)

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. 刪除字符串中的所有相鄰重復(fù)項

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

 

• 題目描述

給出由小寫字母組成的字符串 S，重復(fù)項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。

在 S 上反復(fù)執(zhí)行重復(fù)項刪除操作，直到無法繼續(xù)刪除。

在完成所有重復(fù)項刪除操作后返回最終的字符串。答案保證唯一。

示例：

1. 輸入："abbaca"

2. 輸出："ca"

3. 解釋：例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執(zhí)行刪除操作的重復(fù)項。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項刪除操作，所以最后的字符串為 "ca"。

提示：

1. 1 <= S.length <= 20000

2. S 僅由小寫英文字母組成。

 

• 實現(xiàn)思想

 

• 棧思想。遍歷字符串s，如果棧非空并且棧首不等于遍歷值，將該值追加棧中，如果相等話，將棧首移除。

 

• 代碼實現(xiàn)

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/

 

• 題目描述

 

根據(jù) 逆波蘭表示法，求表達式的值。

有效的運算符包括 + ,  - ,  * ,  / 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。

說明：

整數(shù)除法只保留整數(shù)部分。 給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

示例 1：

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

2. 輸出: 9

3. 解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：((2 + 1) * 3) = 9

示例 2：

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

2. 輸出: 6

3. 解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：(4 + (13 / 5)) = 6

示例 3：

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

2. 輸出: 22

解釋:該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：

((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 + ) * ) 。

逆波蘭表達式主要有以下兩個優(yōu)點：

1. 去掉括號后表達式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據(jù)次序計算出正確結(jié)果。

 

• 實現(xiàn)思想

  • 棧思想。

 

• 代碼實現(xiàn)

 

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/

 

• 題目描述

給定一個數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字。滑動窗口每次只向右移動一位。

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

進階：

你能在線性時間復(fù)雜度內(nèi)解決此題嗎？

提示：

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

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

3. 1 <= k <= nums.length

 

• 實現(xiàn)思想

 

• 定一個單調(diào)遞減隊列，用于保存在滑動窗口中遞減隊列，隊首即為窗口中最大值，每次遍歷過程中需要判斷遍歷值和隊首是否相等，如果相等則需要將該值移除隊列；還需要將遍歷值添加到隊列中，使得隊列中的元素始終是窗口中一次遞減的元素。

 

• 代碼實現(xiàn)

 

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/

 

• 題目描述

 

給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例 1:

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

2. 輸出: [1,2]

示例 2:

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

2. 輸出: [1]

提示：

1. 你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)。

2. 你的算法的時間復(fù)雜度必須優(yōu)于 $O(n \log n)$ , n 是數(shù)組的大小。

3. 題目數(shù)據(jù)保證答案唯一，換句話說，數(shù)組中前 k 個高頻元素的集合是唯一的。

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

 

• 實現(xiàn)思想

 

• 定義一個map用于存儲數(shù)字出現(xiàn)的次數(shù)，然后對map中key值排序，排序順序為降序，取前K個元素。

 

• 代碼實現(xiàn)

 

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