Jeff的隨手筆記

學習當一個前端工程師

0%

用LeetCode寫日記-Day17

Posted on Edited on In

今天來了一題完全不知如何下手的題目，今天真的從頭到尾都是看解答來學習。

Day17: Cache With Time Limit

問題描述：

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

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.

問題難度：Medium

問題限制：

  • 0 <= key, value <= 109
  • 0 <= duration <= 1000
  • 1 <= actions.length <= 100
  • actions.length === values.length
  • actions.length === timeDelays.length
  • 0 <= timeDelays[i] <= 1450
  • actions[i] is one of “TimeLimitedCache”, “set”, “get” and “count”
  • First action is always “TimeLimitedCache” and must be executed immediately, with a 0-millisecond delay

我的學習

這題不會，看解答來學習：

這題需要我們創建一個建構式函數，因此我們先創建一個cache的空物件，它會負責儲存value跟time。

1
2
3
var TimeLimitedCache = function() {
    this.cache={}
};

cache的結構會長這樣：

1
2
3
4
5
6
7
8
9
10
11
{
    key1: {
        value: value1,
        timer: timer1
    },
    key2: {
        value: value2,
        timer: timer2
    },
    // ...
}

接下來我們來處理set，首先題目有提到如果key值存在，因此我們要先用if判斷key值是否存在：

1
2
3
4
5
if (this.cache[key] && this.cache[key].timer) {
			code
    } else {
      code  
    }

之所以加this.cache[key].timer 是為了避免計時器已經被 clearTimeout 清除，或者計時器已經執行完畢。

整行是要確保要設定的key已經存在且尚未過期。

接下來處理兩段code：

  1. 如果條件成立，表示鍵已經存在且未過期。

    1
    2
    3
    4
    5
    6
    clearTimeout(this.cache[key].timer);
        this.cache[key].value = value;
        this.cache[key].timer = setTimeout(() => {
          delete this.cache[key];
        }, duration);
        return true;

    首先我們先清除現有的計時器，防止舊的計時器過期
    然後更新value跟time，並return true

  2. 如果條件不成立，表示鍵在快取中不存在，或者已經過期。

    1
    2
    3
    4
    5
    6
    7
    this.cache[key] = {
          value: value,
          timer: setTimeout(() => {
            delete this.cache[key];
          }, duration)
        };
        return false;

    我們創建一個新的***key***

    return false 表示一個新的鍵值對已經被添加到快取中

接下來我們來處理get ：

1
if (this.cache[key] && this.cache[key].timer) {} else {}

一樣先判斷this.cache[key] && this.cache[key].timer 是否存在。

如果條件成立就按照題目要求，傳回關聯的值。否則返回 -1。

1
2
3
4
5
if (this.cache[key] && this.cache[key].timer) {
    return this.cache[key].value;
  } else {
    return -1;
  }

最後來處理count ，首先我們要先建立一個變數:

1
let count = 0

然後用 for in 迴圈來迭代cache裡的所有key

1
2
3
4
5
6
for (const key in this.cache) {
        if (this.cache[key].timer) {
            count++;
        }
    }
    return count;

我的code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
var TimeLimitedCache = function() {
    this.cache={}
};

/** 
 * @param {number} key
 * @param {number} value
 * @param {number} duration time until expiration in ms
 * @return {boolean} if un-expired key already existed
 */
TimeLimitedCache.prototype.set = function(key, value, duration) {
    if (this.cache[key] && this.cache[key].timer) {
    clearTimeout(this.cache[key].timer);
    this.cache[key].value = value;
    this.cache[key].timer = setTimeout(() => {
      delete this.cache[key]
    }, duration);
    return true;
  } else {
    this.cache[key] = {
      value: value,
      timer: setTimeout(() => {
        delete this.cache[key]
      }, duration)
    };
    return false;
  }
    
};

/** 
 * @param {number} key
 * @return {number} value associated with key
 */
TimeLimitedCache.prototype.get = function(key) {
if (this.cache[key] && this.cache[key].timer) {
    return this.cache[key].value;
  } else {
    return -1;
  }
};

/** 
 * @return {number} count of non-expired keys
 */
TimeLimitedCache.prototype.count = function() {
let count = 0;
  for (const key in this.cache) {
    if (this.cache[key].timer) {
      count++;
    }
  }
  return count;
};

其他解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const TimeLimitedCache = function() {
    this.cache = new Map();  // Using Map so we don't need a size variable
};

TimeLimitedCache.prototype.set = function(key, value, duration) {
    let found = this.cache.has(key);
    if (found) clearTimeout(this.cache.get(key).ref);  // Cancel previous timeout
    this.cache.set(key, {
        value,  // Equivalent to `value: value`
        ref: setTimeout(() => this.cache.delete(key), duration)
    });
    return found;
};

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

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

總結:

學習完後覺得其實沒有到很難啊，但是一拿到題目時真的滿頭問號，這到底要怎麼寫啊！！！