https://leetcode.com/problems/number-of-students-unable-to-eat-lunch
1700. Number of Students Unable to Eat Lunch
齁樓提供PM跟MC兩種貼貼 分別用0跟1表示
全部齁粉站在一queue 每個齁粉喜歡PM或MC
貼貼數量與齁粉數量相等 貼貼被放在一stack
如果queue前面的齁粉喜歡stack頂端的貼貼 他會拿走貼貼
否則他會放下貼貼並回到queue最後面
循環反覆 直至剩下的齁粉都不想拿stack最頂端的貼貼 他們就會去公園
請回傳公園民的數量
Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Front student leaves the top sandwich and returns to the end of the line
making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line
making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students =
[0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line
making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students =
[1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line
making students = [0,1].
- Front student takes the top sandwich and leaves the line making students =
[1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students =
[] and sandwiches = [].
Hence all students are able to eat.
Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3
思路1:
模擬兩個數列出入過程 假如students裡面沒有sandwiches[0] 回傳student的長度
否則繼續模擬 直至students為空 回傳0
Python Code:
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) ->
int:
while students:
if sandwiches[0] not in students:
return len(students)
f = students.pop(0)
if f == sandwiches[0]:
sandwiches.pop(0)
else:
students.append(f)
return 0
思路2:
先開一個list紀錄學生偏好的三明治的數量 之後紀錄sandwiches的初始長度
最後遍歷sandwiches
假如list[sandwich[0]] == 0 就break
假如初始長度為零 break
否則list[sandwich[0]]-1 初始長度-1
最後回傳初始長度
Python Code:
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) ->
int:
counts = [0, 0]
for student in students:
counts[student] += 1
remaining = len(sandwiches)
for sandwich in sandwiches:
if counts[sandwich] == 0:
break
if remaining == 0:
break
counts[sandwich] -= 1
remaining -= 1
return remaining