目錄

基于棧

Ⅰ、1441. 用棧操作構建數組

算法與思路

① 初始化操作序列

② 遍歷數字范圍

③ 判斷并添加操作

④ 提前結束循環

⑤ 返回操作序列

基于隊列

?Ⅰ、1700. 無法吃午餐的學生數量

思路與算法

① 統計學生對三明治的需求：

② 遍歷三明治供應順序：

---

向山而行，你只管往前走

????????????????????????????????—— 25.5.11

基于棧

? ? ? ? 利用棧的數據結構，如：

Ⅰ、1441. 用棧操作構建數組

給你一個數組?target?和一個整數?n。每次迭代，需要從??list = { 1 , 2 , 3 ..., n }?中依次讀取一個數字。

請使用下述操作來構建目標數組?target?：

• "Push"：從?list?中讀取一個新元素， 并將其推入數組中。
• "Pop"：刪除數組中的最后一個元素。
• 如果目標數組構建完成，就停止讀取更多元素。

題目數據保證目標數組嚴格遞增，并且只包含?1?到?n?之間的數字。

請返回構建目標數組所用的操作序列。如果存在多個可行方案，返回任一即可。

示例 1：

輸入：target = [1,3], n = 3
輸出：["Push","Push","Pop","Push"]
解釋： 
讀取 1 并自動推入數組 -> [1]
讀取 2 并自動推入數組，然后刪除它 -> [1]
讀取 3 并自動推入數組 -> [1,3]

示例 2：

輸入：target = [1,2,3], n = 3
輸出：["Push","Push","Push"]

示例 3：

輸入：target = [1,2], n = 4
輸出：["Push","Push"]
解釋：只需要讀取前 2 個數字就可以停止。

提示：

• 1 <= target.length <= 100
• 1 <= n <= 100
• 1 <= target[i] <= n
• target?嚴格遞增

算法與思路

① 初始化操作序列

創建一個空列表?res，用于存儲操作序列（"Push" 或 "Pop"）。初始化一個索引變量?i?為?0，用于遍歷目標數組?target。

② 遍歷數字范圍

使用?for?循環遍歷從?1?到?n?的整數，循環變量為?j。

③ 判斷并添加操作

對于每個?j，檢查?target[i]?是否等于?j：如果相等，說明當前數字在目標數組中，將 "Push" 添加到操作序列?res?中，并將索引?i?加?1，表示已處理完目標數組中的一個元素。如果不相等，說明當前數字不在目標數組中，先將 "Push" 添加到操作序列?res?中，再添加 "Pop"，表示將該數字壓入棧后立即彈出。

④ 提前結束循環

在每次循環中，檢查索引?i?是否大于或等于目標數組?target?的長度。如果是，說明目標數組中的元素已全部處理完，提前結束循環。

⑤ 返回操作序列

循環結束后，返回操作序列?res。

class Solution:def buildArray(self, target: List[int], n: int) -> List[str]:res = []i = 0for j in range(1, n + 1):if target[i] == j:res.append("Push")i += 1else:res.append("Push")res.append("Pop")if i >= len(target):breakreturn res

---

基于隊列

? ? ? ? 利用隊列的數據結構，如：

?Ⅰ、1700. 無法吃午餐的學生數量

學校的自助午餐提供圓形和方形的三明治，分別用數字?0?和?1?表示。所有學生站在一個隊列里，每個學生要么喜歡圓形的要么喜歡方形的。
餐廳里三明治的數量與學生的數量相同。所有三明治都放在一個?棧?里，每一輪：

• 如果隊列最前面的學生?喜歡?棧頂的三明治，那么會?拿走它?并離開隊列。
• 否則，這名學生會?放棄這個三明治?并回到隊列的尾部。

這個過程會一直持續到隊列里所有學生都不喜歡棧頂的三明治為止。

給你兩個整數數組?students?和?sandwiches?，其中?sandwiches[i]?是棧里面第?i???????個三明治的類型（i = 0?是棧的頂部），?students[j]?是初始隊列里第?j???????名學生對三明治的喜好（j = 0?是隊列的最開始位置）。請你返回無法吃午餐的學生數量。

示例 1：

輸入：students = [1,1,0,0], sandwiches = [0,1,0,1]
輸出：0 
解釋：
- 最前面的學生放棄最頂上的三明治，并回到隊列的末尾，學生隊列變為 students = [1,0,0,1]。
- 最前面的學生放棄最頂上的三明治，并回到隊列的末尾，學生隊列變為 students = [0,0,1,1]。
- 最前面的學生拿走最頂上的三明治，剩余學生隊列為 students = [0,1,1]，三明治棧為 sandwiches = [1,0,1]。
- 最前面的學生放棄最頂上的三明治，并回到隊列的末尾，學生隊列變為 students = [1,1,0]。
- 最前面的學生拿走最頂上的三明治，剩余學生隊列為 students = [1,0]，三明治棧為 sandwiches = [0,1]。
- 最前面的學生放棄最頂上的三明治，并回到隊列的末尾，學生隊列變為 students = [0,1]。
- 最前面的學生拿走最頂上的三明治，剩余學生隊列為 students = [1]，三明治棧為 sandwiches = [1]。
- 最前面的學生拿走最頂上的三明治，剩余學生隊列為 students = []，三明治棧為 sandwiches = []。
所以所有學生都有三明治吃。

示例 2：

輸入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
輸出：3

提示：

• 1 <= students.length, sandwiches.length <= 100
• students.length == sandwiches.length
• sandwiches[i]?要么是?0?，要么是?1?。
• students[i]?要么是?0?，要么是?1?。

思路與算法

① 統計學生對三明治的需求：

????????Ⅰ、初始化一個字典?dict?用于記錄每種類型三明治的需求數量。

????????Ⅱ、遍歷學生列表?students，統計每種類型（0 或 1）的學生數量，并更新字典。例如，若有 3 個學生喜歡類型 0 的三明治，dict[0] = 3。

????????Ⅲ、初始化計數器?count?為學生總數，用于記錄剩余未領取三明治的學生數量。

② 遍歷三明治供應順序：

按順序遍歷三明治列表?sandwiches。對于每個三明治：

? ? ? ? Ⅰ、檢查需求是否為 0：若當前三明治類型的需求數為 0（即?dict[sand] == 0），說明沒有學生喜歡這種類型的三明治，無法繼續分配，返回剩余學生數?count。

? ? ? ? Ⅱ、分配三明治：若需求數大于 0，將對應類型的需求數減 1（dict[sand] -= 1），并將剩余學生數減 1（count -= 1）。

? ? ? ? Ⅲ、返回結果：若所有三明治都被分配完畢，返回剩余學生數?count（此時應為 0）。

class Solution:def countStudents(self, students: List[int], sandwiches: List[int]) -> int:dict = {}count = 0for s in students:dict[s] = dict.get(s, 0) + 1count += 1for sand in sandwiches:if dict.get(sand, 0) == 0:return countelse:dict[sand] -= 1count -= 1return count