1845. Seat Reservation Manager
設計一個訂位系統。
1.初始化，它會給你一個n代表有n個位子可以訂，初始時所有位置都是可訂狀態。
2.reserve() 選擇可訂位中數字最小的一個位子並回傳。
3.unreserve(int seatNumber) 取消數字seatNumber的訂位。
這題code比較長 我有放在leetcode比較好讀 https://reurl.cc/m042vl
First Think:
直接用一個陣列去記錄所有未訂位的位子
選擇這個做法的話有Array跟Set可以用
這邊會選擇Set
第一個原因是因為條件有設定元素不會重複
所以我們不用擔心Set無法存重複元素的缺點
然後Set的底層是用Hash Table去實作
他查找元素的時間複雜度是 O(1)
而如果用C#的話還有SortedSet可以用
它在塞進元素的時候就會自動排序好
Approach:
仔細想了一下覺得這個方法不太好
後半段沒有用到的位子會一直佔著陣列位置感覺很浪費
如果用兩個整數min, max去框出未訂位的範圍
我們只要去處理取消的訂位就可以減少浪費
最差的狀況即便所有訂位都被訂過一次再取消
也只是跟直接陣列紀錄一樣而已
後來發現條件設定有寫訂位的時候保證一定有位子可以訂
這代表執行訂位的時候永遠不可能超過n
因此我們根本不需要max紀錄範圍的上限
然後我們在有人取消訂位的時候
如果可以放回min的範圍內就別塞進陣列
這題交了TS版本之後發現複雜度都是100%
想說會不會是TS的解題人數太少
所以又用C#寫了一次效能依然很好
看起來就這樣了
本來我提交完之後覺得minUnreservedSeat這個變數好像可以拔掉
可是拔掉之後測了很多次時間跟空間反而都上升了
我覺得有可能是因為reserve的時候每次要判斷size導致
不然我也不知道為什麼了
原本 []
430ms Beats 100.00%of users with TypeScript
111.76MB Beats 100.00%of users with TypeScript
405ms Beats 97.30%of users with C#
106.08MB Beats 83.78%of users with C#
移除minUnreservedSeat []
424ms Beats 100.00%of users with TypeScript
113.05MB Beats 77.78%of users with TypeScript
432ms Beats 75.68%of users with C#
108.36MB Beats 40.54%of users with C#
TS code:
class SeatManager {
min: number
unreservedSeats: Set<number>
minUnreservedSeat: number
constructor(n: number) {
this.min = 0
this.unreservedSeats = new Set<number>()
this.minUnreservedSeat = Number.MAX_SAFE_INTEGER
}
static #getMinUnreservedSeat = (arr: number[]): number => {
let newMinUnreservedSeat = Number.MAX_SAFE_INTEGER
arr.forEach((value) => {
if (newMinUnreservedSeat > value) newMinUnreservedSeat = value
})
return newMinUnreservedSeat
}
reserve (): number {
if (this.minUnreservedSeat === Number.MAX_SAFE_INTEGER) {
this.min++
return this.min
}
const reserveNumber = this.minUnreservedSeat
this.unreservedSeats.delete(reserveNumber)
this.minUnreservedSeat =
SeatManager.#getMinUnreservedSeat([...this.unreservedSeats.values()])
return reserveNumber
}
unreserve (seatNumber: number): void {
if (seatNumber === this.min) {
this.min