Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

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--
      while (this.unreservedSeats.has(this.min)) {
        this.unreservedSeats.delete(this.min)
        if (this.min === this.minUnreservedSeat) {
          this.minUnreservedSeat = Number.MAX_SAFE_INTEGER
        }
        this.min--
      }
    }
    else {
      this.unreservedSeats.add(seatNumber)
      if (seatNumber < this.minUnreservedSeat) this.minUnreservedSeat =
seatNumber
    }
  }
}

C# code:
public class SeatManager
{
  private int min;
  private HashSet<int> unreservedSeats;
  private int minUnreservedSeat;
  public SeatManager(int n)
  {
    this.min = 0;
    this.unreservedSeats = new HashSet<int>();
    this.minUnreservedSeat = int.MaxValue;
  }
  private static int GetMinUnreservedSeat(IEnumerable<int> arr)
  {
    var newMinUnreservedSeat = int.MaxValue;
    foreach (var value in arr)
      if (newMinUnreservedSeat > value) newMinUnreservedSeat = value;
    return newMinUnreservedSeat;
  }
  public int Reserve()
  {
    if (this.minUnreservedSeat == int.MaxValue)
    {
      this.min++;
      return this.min;
    }
    var reserveNumber = this.minUnreservedSeat;
    this.unreservedSeats.Remove(reserveNumber);
    this.minUnreservedSeat =
SeatManager.GetMinUnreservedSeat(unreservedSeats);
    return reserveNumber;
  }

  public void Unreserve(int seatNumber)
  {
    if (seatNumber == this.min)
    {
      this.min--;
      while (this.unreservedSeats.Contains(this.min))
      {
        this.unreservedSeats.Remove(this.min);
        if (this.min == this.minUnreservedSeat)
        {
          this.minUnreservedSeat = int.MaxValue;
        }
        this.min--;
      }
    }
    else
    {
      this.unreservedSeats.Add(seatNumber);
      if (seatNumber < this.minUnreservedSeat) this.minUnreservedSeat =
seatNumber;
    }
  }
}

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699242354.A.FF3.html
推 SecondRun: 大師