【LeetCode熱題100】打卡第33天：環(huán)形鏈表&LRU緩存

?前言

大家好，我是知識汲取者，歡迎來到我的LeetCode熱題100刷題專欄！

精選 100 道力扣（LeetCode）上最熱門的題目，適合初識算法與數(shù)據(jù)結構的新手和想要在短時間內高效提升的人，熟練掌握這 100 道題，你就已經具備了在代碼世界通行的基本能力。在此專欄中，我們將會涵蓋各種類型的算法題目，包括但不限于數(shù)組、鏈表、樹、字典樹、圖、排序、搜索、動態(tài)規(guī)劃等等，并會提供詳細的解題思路以及Java代碼實現(xiàn)。如果你也想刷題，不斷提升自己，就請加入我們吧！QQ群號：827302436。我們共同監(jiān)督打卡，一起學習，一起進步。

博客主頁??：知識汲取者的博客

LeetCode熱題100專欄??：LeetCode熱題100

Gitee地址??：知識汲取者 (aghp) - Gitee.com

Github地址??：Chinafrfq · GitHub

題目來源??：LeetCode 熱題 100 - 學習計劃 - 力扣（LeetCode）全球極客摯愛的技術成長平臺

PS：作者水平有限，如有錯誤或描述不當?shù)牡胤?，懇請及時告訴作者，作者將不勝感激

環(huán)形鏈表

??題目

原題鏈接：142.環(huán)形鏈表II

??題解

• 解法一：Set集合

  昨天剛寫完【LeetCode熱題100】打卡第32天的題目，其中就遇到 環(huán)形鏈表I，也是使用這種方式解決的O(∩_∩)O

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          Set<ListNode> set = new HashSet<>();
          while (head != null) {
              if (!set.add(head)) {
                  return head;
              }
              head = head.next;
          }
          return null;
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(n)$
  • 空間復雜度：$O(n)$

  其中 $n$ 為數(shù)組中元素的個數(shù)

• 解法二：快慢指針

  這個快慢指針用起來就要比【LeetCode熱題100】打卡第32天的題目 的那道環(huán)形鏈表I 要難的多了

  詳解參考 K神，真的是強，佩服b(￣▽￣)d，這里我給出一些我的理解

  假設head到環(huán)入口出要走a步，環(huán)的節(jié)點數(shù)為b，則：

  1. fast于slow相遇，fast一定是比slow多走nb步

     $s,f=2s=s+nb\to s=nb$

  2. a+nb一定是在環(huán)入口出

  3. 第一次相遇后，我們將fast重置到head處，這樣就能保障fast和slow相遇一定是是a+nb，此時兩者在環(huán)入口相遇

     $f=0,s=nb\to f=a,s=a+nb$

  這里面具有很嚴密的數(shù)據(jù)邏輯推理在里面！

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          ListNode fast = head;
          ListNode slow = head;
          while (fast != null){
              slow = slow.next;
              fast = fast.next;
              if (fast!=null){
                  fast = fast.next;
              }
              if (fast == slow){
                  break;
              }
          }
          if (fast==null){
              return null;
          }
          fast = head;
          while (fast!=slow){
              slow = slow.next;
              fast = fast.next;
          }
          return fast;
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(n)$
  • 空間復雜度：$O(n)$

  其中 $n$ 為數(shù)組中元素的個數(shù)

LRU緩存

??題目

原題鏈接：146.LRU緩存

??題解

• 解法一：Map標記法（超時，22個示例數(shù)據(jù)過了20個）

  這是最開始的思路，直接使用雙Map，一個Map作為緩存，一個Map用于記錄key的淘汰優(yōu)先級，每次進行get或put操作時，未操作的key的淘汰優(yōu)先級都自增1，如果緩存已滿，則根據(jù)淘汰優(yōu)先級進行淘汰?？偟膩碚f這個思路還是挺簡單的，但是這代碼看著就像“屎山代碼”w(?Д?)w，感覺可以進行優(yōu)化

  

  

  class LRUCache {
  
      // 緩存
      private Map<Integer, Integer> cache;
      // 用于標記，值越大越優(yōu)先淘汰
      private Map<Integer, Integer> flag;
      // 最大容量
      private int MAX_CAPACITY;
  
  
      public LRUCache(int capacity) {
          MAX_CAPACITY = capacity;
          cache =  new HashMap<>(capacity);
          flag = new HashMap<>(capacity);
      }
  
      /**
       * 從緩存中獲取值
       */
      public int get(int key) {
          if (cache.containsKey(key)){
              // 當前元素置0，其它元素值+1
              flag.put(key, 0);
              increment(key);
              return cache.get(key);
          }
          return -1;
      }
  
      /**
       * 除key以外的都自增
       */
      private void increment(int key) {
          for (Integer i : flag.keySet()) {
              if (i != key){
                  flag.put(i, flag.get(i)+1);
              }
          }
      }
  
      /**
       * 往緩存中添加元素
       */
      public void put(int key, int value) {
          if (cache.size() < MAX_CAPACITY){
              // 緩存容量足夠，直接添加，并將新加入元素標記值置為初值0
              cache.put(key, value);
              flag.put(key, 0);
              increment(key);
              return;
          }
          if (cache.containsKey(key)){
              // 緩存容量不夠，但是當前添加的key已在緩存中存在，直接更新即可
              cache.put(key, value);
              flag.put(key, 0);
              increment(key);
              return;
          }
          // 緩存容量不夠且key不在緩存中，使用 LRU 策略淘汰緩存中的數(shù)據(jù)
          int i = getDieOutKey();
          cache.remove(i);
          cache.put(key, value);
          flag.put(key, 0);
          increment(key);
      }
  
      /**
       * 獲取淘汰元素的索引
       */
      private int getDieOutKey() {
          int max = Integer.MIN_VALUE;
          int key = 0;
          for (Integer i : flag.keySet()) {
              if (flag.get(i)>max){
                  max = flag.get(i);
                  key = i;
              }
          }
          flag.remove(key);
          return key;
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(n)$，每次put和get都需要調用increment方法，increment方法需要遍歷整個map，getDieOutKey方法也需要遍歷整個map，時間復雜度也是$O(n)$，但兩者沒有嵌套，所以總的時間復雜度是$O(n)$
  • 空間復雜度：$O(n)$

  其中 $n$ 為緩存的大小

  代碼優(yōu)化：使用隊列代替Map標記（時間優(yōu)化）

  上面我們是利用Map集合對存入緩存中的元素進行一個標記，每次往緩存中存入和獲取，都需要遍歷一遍 flag ，并且刪除時也需要遍歷一遍 flag，這就導致雖然看著時間復雜度是$(n)$，但是對于頻繁的操作耗時是非常多的。

  上面的map標記法，我們可以知道最大耗時在于定位 flag 中最大的value，為了解決定位問題，我們可以采用隊列，而不是map，隊列具有先進先出的特點（隊尾進，對頭出），這就意味著我們可以將最舊的元素放到對頭，最新的元素放到隊尾。

  

  

  class LRUCache {
  
      // 緩存
      private Map<Integer, Integer> map;
      // 用于LRU淘汰
      private Queue<Integer> queue;
      // 最大容量
      private int MAX_CAPACITY;
  
      public LRUCache(int capacity) {
          MAX_CAPACITY = capacity;
          map = new HashMap<>(capacity);
          queue = new LinkedList<>();
      }
  
      public int get(int key) {
          if (map.containsKey(key)){
              queue.remove(key);
              queue.offer(key);
              return map.get(key);
          }
          return -1;
      }
  
      public void put(int key, int value) {
          if (map.containsKey(key)){
              // 緩存中存在該key，直接更新
              queue.remove(key);
              queue.offer(key);
              map.put(key, value);
              return;
          }
          if (map.size() < MAX_CAPACITY){
              // 緩存不存在該key，但當前緩存容量足夠，直接添加
              queue.offer(key);
              map.put(key, value);
              return;
          }
          // 緩存容量不足，移除最先進入隊列的元素
          int first = queue.poll();
          queue.add(key);
          map.remove(first);
          map.put(key, value);
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(n)$，queue.remove()方法需要遍歷鏈表，時間復雜度是$O(n)$
  • 空間復雜度：$O(n)$

  n為緩存中最大能存儲元素的個數(shù)

  PS：顯然這段代碼比上上面那段代碼就要好的多了，但是提交只能夠擊敗5%的 Java選手，這說明還有更好的方法

• 解法二：利用LinkedHashMap

  LinkedHashMap底層是使用一個 Map+雙向鏈表，LinkedHashMap有一個最大容量

  class LRUCache extends LinkedHashMap<Integer, Integer>{
      // 最大容量
      private int capacity;
      
      public LRUCache(int capacity) {
          // 調用構造方法，第三個參數(shù)設置為true時，當LinkedHashMap達到最大容量時
          // 底層回采用LRU策略，移除最舊的元素
          super(capacity, 0.75F, true);
          this.capacity = capacity;
      }
  
      public int get(int key) {
          return super.getOrDefault(key, -1);
      }
  
      public void put(int key, int value) {
          super.put(key, value);
      }
  
      /**
      * 設置淘汰時機，當超過最大容量時按照LRU策略淘汰最舊的值
      */
      @Override
      protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
          return size() > capacity; 
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(1)$
  • 空間復雜度：$O(n)$

  其中 $n$ 為緩存中元素的最大個數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-551945.html

  參照LinkedHashMap源碼手寫一個簡易版的LinkedHashMap：

  前面我們使用隊列進行移除操作，時間復雜度是$O(n)$，因為隊列底層是采用了單鏈表，單鏈表刪除中間節(jié)點需要先遍歷鏈表定位到要刪除的節(jié)點的前驅節(jié)點，而現(xiàn)在我們使用一個雙鏈表數(shù)據(jù)結構，我們直接可以通過 前驅指針pre 定位到要刪除的節(jié)點前驅節(jié)點，進行刪除操作，這就大大提高了刪除的效率，從而提高了時間，但是提高了額外的內存開銷（典型的空間換時間）

  

  class LRUCache {
  
      /**
       * 定義一個雙鏈表
       */
      private class DLinkedList {
          int key;
          int value;
          // 前驅指針，用于維護當前節(jié)點與前驅節(jié)點的關系
          DLinkedList pre;
          // 后繼指針，用于維護當前節(jié)點與后繼節(jié)點的關系
          DLinkedList next;
          public DLinkedList() {}
          public DLinkedList(int key, int value) {
              this.key = key;
              this.value = value;
          }
      }
  
      /**
       * 緩存最大容量
       */
      private int capacity;
      /**
       * 緩存中的元素的個數(shù)（空間換時間）
       */
      private int size;
      /**
       * 雙鏈表的頭節(jié)點指針
       */
      DLinkedList head;
      /**
       * 雙鏈表的尾節(jié)點指針
       */
      DLinkedList tail;
      /**
       * 緩存
       */
      private Map<Integer, DLinkedList> cache = new HashMap<>();
  
  
      public LRUCache(int capacity) {
          this.capacity = capacity;
          this.size = 0;
          this.head = new DLinkedList();
          this.tail = new DLinkedList();
          this.head.next = this.tail;
          this.tail.pre = this.head;
      }
  
      /**
       * 從緩存中取值
       */
      public int get(int key) {
          DLinkedList node = cache.get(key);
          if (node == null) {
              // 緩存未命中，直接返回-1
              return -1;
          }
          // 緩存命中，則更新雙鏈表（將命中節(jié)點更新為雙鏈表的頭節(jié)點）
          moveToHead(node);
          return node.value;
      }
  
      /**
       * 往緩存中存值
       */
      public void put(int key, int value) {
          DLinkedList node = cache.get(key);
          if (node != null) {
              // 緩存命中，則更新雙鏈表并直接返回命中的值
              node.value = value;
              moveToHead(node);
              return;
          }
          // 緩存未命中，需要判斷當前緩存的容量是否充足
          if (size == capacity) {
              // 緩存容量已滿，需要采用LRU策略移除最舊的值（也就是雙鏈表的尾節(jié)點）
              DLinkedList tailNode = remove(tail.pre);
              cache.remove(tailNode.key);
              size--;
          }
          // 將新增的節(jié)點添加到鏈表頭部，并存入緩存
          DLinkedList newNode = new DLinkedList(key, value);
          add(newNode);
          cache.put(key, newNode);
          size++;
      }
  
      /**
       * 將節(jié)點更新為雙鏈表的頭節(jié)點
       */
      public void moveToHead(DLinkedList node) {
          // 先移除，后添加，即可將節(jié)點更新為頭節(jié)點
          remove(node);
          add(node);
      }
  
      /**
       * 移除節(jié)點（并返回被移除的節(jié)點）
       */
      private DLinkedList remove(DLinkedList node) {
          if (node.next == tail) {
              // 要移除的節(jié)點是尾節(jié)點
              node.pre.next = tail;
              tail.pre = node.pre;
          } else {
              // 要移除的節(jié)點是中間節(jié)點
              node.pre.next = node.next;
              node.next.pre = node.pre;
          }
          return node;
      }
  
      /**
       * 添加節(jié)點（從雙鏈表的頭部添加）
       */
      private void add(DLinkedList node) {
          node.pre = head;
          node.next = head.next;
          head.next.pre = node;
          head.next = node;
      }
  
  }
  

  復雜度分析：

  • 時間復雜度：$O(1)$
  • 空間復雜度：$O(n)$

  其中 $n$ 為緩存中元素的最大個數(shù)

到了這里，關于【LeetCode熱題100】打卡第33天：環(huán)形鏈表&LRU緩存的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！