LeetCode JavaScript 30 Days Challenge – Day14 – 2622. Cache With Time Limit

    AllenLi
    LeetCode JavaScript 30 Days Challenge

    Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.

    編寫一個允許取得和設定 key-value 鍵，然而持續時間與每個鍵有相關聯。

    The class has three public methods:
    set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.
    get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.
    count(): returns the count of un-expired keys.

    該類具有三個公開的方法：
- set(key, value, duration)：接受一個整數鍵、一個整數值和一個以毫秒為單位的持續時間。持續時間結束後，密鑰則無法訪問。如果已經存在相同且未過期密鑰，則該方法應回傳 true，否則回傳 false。如果密鑰已經存在，則應覆蓋該整數值和持續時間。
- get(key)：如果存在未過期的鍵，它應該回傳關聯的值，否則它應該回傳 -1。
- count()：回傳未過期的密鑰次數。

    Example 1:

    Input: 
["TimeLimitedCache", "set", "get", "count", "get"]
[[], [1, 42, 100], [1], [], [1]]
[0, 0, 50, 50, 150]
Output: [null, false, 42, 1, -1]

    Example 2:

    Input: 
["TimeLimitedCache", "set", "set", "get", "get", "get", "count"]
[[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []]
[0, 0, 40, 50, 120, 200, 250]
Output: [null, false, true, 50, 50, -1]

    solution:
    我們先定義了一個 TimeLimitedCache 類別，它是一個有時間限制的結構。它使用 Map 來儲存整數鍵。當呼叫 set 方法時，它會將整數鍵存入 cache 物件並設定一個計時器，在指定的時間後自動刪除該項目。使用 get 方法可以獲取鍵對應的值，並使用 count 方法計算 cache 中的項目數量。

    Code 1: prototype BigO(1)

    var TimeLimitedCache = function() {
  this.cache = new Map()
}

TimeLimitedCache.prototype.set = function(key, value, duration) {
  const alreadyExists = this.cache.get(key)
  if (alreadyExists) {
    clearTimeout(alreadyExists.timeoutId)
  }
  const timeoutId = setTimeout(() => {
    this.cache.delete(key)
  }, duration)
  this.cache.set(key, {
    value,
    timeoutId
  })
  return Boolean(alreadyExists);
}

TimeLimitedCache.prototype.get = function(key) {
  if (this.cache.has(key))
    return this.cache.get(key).value;
  return -1;
}

TimeLimitedCache.prototype.count = function() {
  return this.cache.size;
}

    FlowChart:
    Example 1

    ["TimeLimitedCache", "set"       , "get", "count", "get"]
[       []         , [1, 42, 100], [1]  ,    []  , [1]  ]
[        0         ,       0     ,  50  ,    50  , 150  ]

1. null //建立 TimeLimitedCache 模型的物件。
2. false //建立 TimeLimitedCache.prototype.set(1, 42, 100) {}。
3. 42 //取得 TimeLimitedCache.prototype.get(42)。
4. 1 //回傳 TimeLimitedCache.prototype.count(1)。
5. -1 //超過時間，key失效，回傳-1。
=> [null, false, 42, 1, -1]

    Example 2

    ["TimeLimitedCache",    "set"    ,    "set"    , "get", "get", "get", "count" ]
[        []        , [1, 42, 50] , [1, 50, 100],  [1] ,  [1] ,  [1] ,    []   ]
[        0         ,      0      ,      40     ,   50 ,  120 ,  200 ,   250   ]

1. null //建立 TimeLimitedCache 模型的物件。
2. false //建立 TimeLimitedCache.prototype.set(1, 42, 50) {}。
3. false //建立(覆蓋) TimeLimitedCache.prototype.set(1, 50, 100) {}。時間重新計算。
4. 50 //取得 TimeLimitedCache.prototype.get(50)。
5. 50 //取得 TimeLimitedCache.prototype.get(50)。
6. -1 //超過時間，key失效，回傳-1。

=> [null, false, true, 50, 50, -1]

    Code 2: class BigO(1)

    class TimeLimitedCache {
  cache = new Map()

  set(key, value, duration) {
    const alreadyExists = this.cache.get(key)
    if (alreadyExists) {
      clearTimeout(alreadyExists.timeoutId)
    }
    const timeoutId = setTimeout(() => {
      this.cache.delete(key)
    }, duration)
    this.cache.set(key, {
      value,
      timeoutId
    })
    return Boolean(alreadyExists);
  }
  
  get(key) {
    if (this.cache.has(key))
      return this.cache.get(key).value;
    return -1;
  }
  
  count() {
    return this.cache.size;
  }
};

    Related Posts