LeetCode题目

1. LeetCode题目

   1. LFU算法

      1. LFU算法是什么

         昨天，我们手写了一个LRU算法，而LFU算法也是一种缓存淘汰算法。
         LFU算法全名Least Frequently Used ，最近最少使用。

      2. LFU算法的设计思路

         LFU算法满足以下几点：1、get方法返回key对应的val；2、只要使用get或者put方法访问一次key对应的元素，该元素的频次freq+1；3、如果容量满时进行put，则需要将freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧的那一个

         基于LFU算法的要求，我们使用多个基础数据结构进行设计：1、使用HashMap存储key和val，满足O(1)复杂度的key-val查询；2、使用一个HashMap存储key和freq，满足使用get或put访问一个key，则让freq+1；3、需要freq到key的映射，用来找到freq对应最小的key，同时可能有多个key拥有相同的freq，所以freq对key是一对多的关系，即一个freq对应一个key的列表，同时，key列表存在时序的，便于快速查找并删除最旧的key，使用HashMap+LinkedHashSet；4、将freq最小的key删除，快速得到当前所有key最小的freq是多少。想要O(1)，就用一个变量minFreq来记录当前最小的freq，根据该freq瞬间得到对应的val列表

      3. LFU的基本数据结构

          class LFU {
         
              // key 到 val 的映射
              HashMap<Integer, Integer> keyToVal;
         
              // key 到 freq 的映射
              HashMap<Integer, Integer> keyToFreq;
         
              // freq 到 key 列表的映射
              HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
         
              // 记录最小的频次
              int minFreq;
         
              // 记录 LFU 缓存的最大容量
              int cap;
         
              public LFUCache(int capacity) {
                  keyToVal = new HashMap<>();
                  keyToFreq = new HashMap<>();
                  freqToKeys = new HashMap<>();
                  this.cap = capacity;
                  this.minFreq = 0;
              }
         
              public int get(int key) {
                  // 没有key，返回-1
                  if (!keyToVal.containsKey(key)) {
                      return -1;
                  }
                  // 有，则让freq+1,然后返回val
                  increaseFreq(key);
                  return keyToVal.get(key);
              }
         
              public void put(int key, int val) {
                  if (keyToVal.containsKey(key)) {
                      // key存在，则修改key对应的val，并且让freq+1
                      keyToVal.put(key, val);
                      increaseFreq(key);
                  } else {
                      // key不存在，则添加元素。添加前判断容量
                      if (this.cap <= keyToVal.size()) {
                          // 容量不足，删除元素
                          removeMinFreqKey();
                      }
                      // 直接插入
                      keyToVal.put(key, val);
                      keyToFreq.put(key, 1);
                      freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
                      // 因为插入后，freq为1，freq最少为1，因此还要添加freq为1的key对应的key列表
                      freqToKeys.get(1).add(key);
                      // 设置最小freq为1
                      this.minFreq = 1;
                  }
              }
         
              /**LFU算法核心**/
         
              /**
              * 更新key对应的freq
              */
              private void increaseFreq(int key) {
                  // 获取当前key对应的当前freq
                  int freq = keyToFreq.get(key);
                  // 更新key-freq映射
                  keyToFreq.put(key, freq + 1);
                  // 更新freq-key映射
                  // 将 key 从 freq 对应的列表中删除
                  freqToKeys.get(freq).remove(key);
                  // 将key放入freq+1的对应val列表中
                  freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
                  freqToKeys.get(freq + 1).add(key);
                  // 此时，如果freq对应的val列表为空，则移除该freq
                  if (freqToKeys.get(freq).isEmpty()) {
                      freqToKeys.remove(freq);
                      // 如果这个 freq 恰好是 minFreq，更新 minFreq
                      if (freq == this.minFreq) {
                          this.minFreq++;
                      }
                  }
         
              }
         
              /**
              * 删除元素
              */
              private void removeMinFreqKey() {
         
                  // 获取最小的freq对应的key列表
                  LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
                  // 列表表头的元素，就是应该删除的key。获取该key
                  Integer deleteKey = keyList.iterator().next();
         
                  // 删除列表中对应的该key
                  keyList.remove(deleteKey);
                  if (keyList.isEmpty()) {
                      // 如果删除后该列表为空，则应该清除该freq-key列表的映射关系
                      freqToKeys.remove(this.minFreq);
                  }
         
                  // 删除key-val映射中的key
                  keyToVal.remove(deleteKey);
         
                  // 删除key-freq映射中的key
                  keyToFreq.remove(deleteKey);
         
              };
         
          }