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