人善交videohd另类,日韩欧美福利,日本黄色视频官网,日日干日日插,成人黄色在线免费观看,一区二,色妞ww精品视频7777nga,中国老太卖婬视频

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

說明:

你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。
假設(shè)所有操作都是有效的（例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。

實現(xiàn)思想
- 定義兩個棧，棧A和棧B，棧A負(fù)責(zé)接收數(shù)據(jù)，棧B負(fù)責(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)棧的下列操作：

push(x) -- 元素 x 入棧
pop() -- 移除棧頂元素
top() -- 獲取棧頂元素
empty() -- 返回棧是否為空

注意:

你只能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
你所使用的語言也許不支持隊列。你可以使用 list 或者 deque（雙端隊列）來模擬一個隊列 , 只要是標(biāo)準(zhǔn)的隊列操作即可。
你可以假設(shè)所有操作都是有效的（例如, 對一個空的棧不會調(diào)用 pop 或者 top 操作）。

實現(xiàn)思想

定義兩個隊列，隊列A和隊列B，隊列A只負(fù)責(zé)接收數(shù)據(jù)，隊列B真正存儲數(shù)據(jù)，當(dāng)數(shù)據(jù)push進(jìn)來，會先由隊列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/

題目描述

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。

示例 1:

輸入: "()"
輸出: true

示例 2:

輸入: "()[]{}"
輸出: true

示例 3:

輸入: "(]"
輸出: false

示例 4:

輸入: "([)]"
輸出: false

示例 5:

輸入: "{[]}"
輸出: 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ù)項刪除操作后返回最終的字符串。答案保證唯一。

示例：

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

提示：

1 <= S.length <= 20000
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. 逆波蘭表達(dá)式求值

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

題目描述

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

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

說明：

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

示例 1：

輸入: ["2", "1", "+", "3", " * "]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9

示例 2：

輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：(4 + (13 / 5)) = 6

示例 3：

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

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

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

逆波蘭表達(dá)式：是一種后綴表達(dá)式，所謂后綴就是指運(yùn)算符寫在后面。

平常使用的算式則是一種中綴表達(dá)式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

該算式的逆波蘭表達(dá)式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。

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

去掉括號后表達(dá)式無歧義，上式即便寫成 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ù)字?；瑒哟翱诿看沃幌蛴乙苿右晃?。

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

進(jìn)階：

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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
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:

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

示例 2:

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

提示：

你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)。
你的算法的時間復(fù)雜度必須優(yōu)于 $O(n \log n)$ , n 是數(shù)組的大小。
題目數(shù)據(jù)保證答案唯一，換句話說，數(shù)組中前 k 個高頻元素的集合是唯一的。
你可以按任意順序返回答案。

實現(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]
}

隊列專題