23.01.30 Today’s Leetcode

N-th Tribonacci Number (easy)

Dynamic Programming

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0] * (n + 1)
        if n == 0:
            return 0
        if n <= 2:
            return 1
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(n - 2):
            dp[i + 3] = dp[i] + dp[i + 1] + dp[i + 2]
        return dp[n]

LRU Cache (medium)

Double Linked List와 Dict를 이용한 방법 : link

class LRUCache:

    def __init__(self, capacity: int):
        self.cache_key = dict()
        self.cache_time = dict()
        self.capacity = capacity
        self.used = 0
        self.time = 1
        

    def get(self, key: int) -> int:
        self.cache_time[key] = self.time
        self.time += 1
        # print(self.cache_key)
        return self.cache_key.get(key, -1)
        

    def put(self, key: int, value: int) -> None:
        if key in self.cache_key:
            self.cache_key[key] = value
            self.cache_time[key] = self.time
        else:
            if self.used < self.capacity:
                self.cache_key[key] = value
                self.cache_time[key] = self.time
                self.used += 1
            else:
                if key not in self.cache_key:
                    # evict the LRU cache
                    dkey = self.find_lru()
                    del self.cache_key[dkey]
                    del self.cache_time[dkey]
                    # print('delete : ', dkey)

                self.cache_key[key] = value
                self.cache_time[key] = self.time
        
        self.time += 1
        # print(self.cache_time)

    def find_lru(self):
        min_time = 10**9
        lru = -1
        for key in self.cache_key.keys():
            if self.cache_time[key] < min_time:
                min_time = self.cache_time[key]
                lru = key
        return lru

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)