[LeetCode] 146. LRU Cache

• Problem: 實作 LRU Cache data structure and get/put operations
• Limitation: O(1) time complexity
• Note:
• get 與 put 都包含了 find 的 operation, 若需要 O(1), 則需要 hash table (unordered_map)
• insert 與 pop: 若 insert (push), pop 都是 push / pop back的話, linked list 或是 vector container 都可以達到 O(1) 的 complexity
• move: 但 LRU 包含了將最近使用的 entry 移動到 begin, 這只有 linked list 能達成
• 要明確了解 get/put 的動作, e.g. put 若是 put 同樣 key, 不同 value, 則 value 應更新
• Concept:
• 較無演算發的要求, 畢竟 LRU 本身就是演算法的概念
• 相當於在考 data structure design, 可知要實作 hash table 找 entry (key 做 hash, value 為 pointer to cache entry), 並用 linked list 來maintain cache entries (key, value) 的 pair
• Implementation:

• class LRUCache {
  public:
      LRUCache(int capacity) {
          m_capacity = capacity;
      }   
      
      int get(int key) {
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend())
          {   
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              return it->second->second;
          }   
          else
              return -1; 
      }   
      
      void put(int key, int value) {
          // 1. find if it alread exists, if yes, move to begin, else insert it
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend()) {
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              // Note: this value may differ from original one, we need to update value
              it->second->second = value;
          } else {
              // check if size reaches capacity
              if (m_cache.size() >= m_capacity) {
                  // a. remove cache entry
                  it = m_hash.find(m_cache.back().first);
                  //cout << "m_cache.back().first: " << m_cache.back().first << endl;
                  m_hash.erase(it);
                  // b. remove LRU
                  m_cache.pop_back();
              }
              m_cache.emplace(m_cache.begin(), make_pair(key, value));
              m_hash.insert(make_pair(key, m_cache.begin()));
          }
      }
  
  private:
      // O(1) to move, insert, delete nodes, we need list data structure
      // for the given data, we need a pair to store both key & value
      list< pair > m_cache;
  
      // max cache size
      int m_capacity;
  
      // for O(1) to find, we need a hash table which we use map here
      unordered_map >::iterator> m_hash;
  };
  

[LeetCode] 23. merge k sorted lists

• Problems: merge k 個 sorted 的 lists
• Solution:
• 延續 21 merge two lists, iteratively 將 k 個中的 lists 兩兩 merge 即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeLists(ListNode *l1, ListNode *l2)
    {
        // ref to problem 22, merge two sorted list
        if (NULL == l1) return l2;
        if (NULL == l2) return l1;
        
        if (l1->val < l2->val) {
            l1->next = mergeLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeLists(l1, l2->next);
            return l2;
        }
    }

    ListNode* mergeKLists(vector& lists) {
        // merge 2 by 2 lists
        size_t iters = lists.size() / 2;
        while (iters > 0) {
            iters = lists.size() / 2;
            for (size_t i = 0; i < iters; i++){
                lists[i] = mergeLists(lists[i], lists[lists.size() - 1 - i]);
            }

            lists.erase(lists.begin() + iters + (1 == lists.size() % 2), lists.end());
        }
        return (lists.size() > 0) ? lists[0] : NULL;
    }
};

[LeetCode] 21 Merge Two Sorted Lists

• Problem: merge 兩個已排序的 lists
• Solution: 
• 可以直接 iteratively 比較兩個 list 元素, 一個一個 push
• recursive
• 終止條件: list0 或 list1已到結尾, 則 return 另一個 list
• 當前判斷:
• 將最小元素的 next 指向 recursive return 回來的 list
• Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (NULL == l1) return l2;
        if (NULL == l2) return l1;
        
        if (l1->val < l2->val) 
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
            
    }
};