前往
大廳
主題

LeetCode - 1700. Number of Students Unable to Eat Lunch 解題心得

Not In My Back Yard | 2023-01-06 12:00:09 | 巴幣 0 | 人氣 359

題目連結:


題目意譯:
學校餐廳在午餐時段提供著圓形和方形的三明治,依序以數字 0 和數字 1 表示。所有學生排成一列。每位學生只喜歡方形或是指喜歡圓形的三明治。

餐廳的三明治數量等同於學生的數量。所有三明治疊成了一堆。每一步之中:
如果佇列最前面的學生正好喜歡現在疊在最上面的三明治,則他會將其拿走並離開隊伍。
反之,他將忽視該三明治並回到隊伍的結尾重新排隊。

以上過程將持續到隊伍中沒有任何學生想要把堆在最上面的三明治拿走,因此這些學生將無法進食。

你被給定兩整數陣列 students 和 sandwiches,其中 sandwiches[i] 代表堆疊中第 i 個三明治的種類(i = 0 代表著堆疊的頂端),而 students[j] 為在一開始的隊伍中的第 j 名學生之偏好(j = 0 代表著佇列的開頭)。回傳無法進食的學生之數量。

限制:
1 ≦ students.length, sandwiches.length ≦ 100
students.length == sandwiches.length
sandwiches[i] 只會是 0 或是 1。
students[i] 只會是 0 或是 1。



範例測資:
範例 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


解題思維:
假設一開始喜歡圓形(0)三明治的學生有 X 人、喜歡方形(1)的則有 Y 人。之後的人數變化將會寫作 X' 和 Y'。

而問題敘述描述的過程之「人數變化」本身等價於:
當現在頂端的三明治為「0」時,如果此時 X' 已經歸零了,則代表剩下的 Y' 人都不會拿走「0」,因此回傳 Y';反之,則 X' 人中會有人拿走頂端的三明治,因此 X' 減去 1。

同理,當頂端的三明治是「1」時,檢查 Y' 是不是歸零了。如果是,則回傳 X';反之,將 Y' 減去 1。

而如果所有三明治都被拿完了,又加上人數 == 三明治數量,因此此時回傳 0 即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作