0801学习

面试 leetcode学习
    1. 单词替换-字节
      在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
      现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
      你需要输出替换之后的句子。
      示例 1：
      输入：dictionary = [“cat”,”bat”,”rat”], sentence = “the cattle was rattled by the battery”
      输出：”the cat was rat by the bat”
  1. public class PreWords
  2. {
  3.     public char Char;
  4.     public bool IsWord;
  5.     public Dictionary<char, PreWords> Next = new Dictionary<char, PreWords>();
  6. 

  7.     public PreWords(char c, bool isWord)
  8.     {
  9.         Char = c;
  10.         IsWord = isWord;
  11.     }
  12. }
  13. 

  14. private Dictionary<char, PreWords> __dictionary = new Dictionary<char, PreWords>();
  15. 

  16. public string ReplaceWords(IList<string> dictionary, string sentence)
  17. {
  18.     foreach (var str in dictionary)
  19.     {
  20.         var first = str[0];
  21.         if (!__dictionary.TryGetValue(first, out var p))
  22.         {
  23.             p = new PreWords(first, false);
  24.             __dictionary[first] = p;
  25.         }
  26. 

  27.         for (int j = 0; j < str.Length;)
  28.         {
  29.             if (j == str.Length - 1)
  30.             {
  31.                 p.IsWord = true;
  32.                 break;
  33.             }
  34. 

  35.             if (!p.Next.TryGetValue(str[++j], out var next))
  36.             {
  37.                 next = new PreWords(str[j], false);
  38.                 p.Next[str[j]] = next;
  39.             }
  40. 

  41.             p = next;
  42.         }
  43.     }
  44. 

  45.     var successores = sentence.Split();
  46.     var sb = new StringBuilder();
  47.     foreach (var successor in successores)
  48.     {
  49.         __ReplaceStr(successor, sb);
  50.     }
  51. 

  52.     sb.Remove(sb.Length - 1, 1);
  53.     return sb.ToString();
  54. }
  55. 

  56. private void __ReplaceStr(string successor, StringBuilder sb)
  57. {
  58.     if (successor.Length > 0)
  59.     {
  60.         var first = successor[0];
  61.         if (__dictionary.TryGetValue(first, out var p))
  62.         {
  63.             if (p.IsWord)
  64.             {
  65.                 sb.Append(first);
  66.                 sb.Append(" ");
  67.             }
  68.             else
  69.             {
  70.                 var index = 1;
  71.                 var find = false;
  72.                 for (; index < successor.Length; index++)
  73.                 {
  74.                     if (p.Next.TryGetValue(successor[index], out var next))
  75.                     {
  76.                         p = next;
  77.                         if (!p.IsWord) continue;
  78.                         find = true;
  79.                     }
  80. 

  81.                     break;
  82.                 }
  83. 

  84.                 sb.Append(find ? successor.Substring(0, index + 1) : successor);
  85.                 sb.Append(" ");
  86.             }
  87.         }
  88.         else
  89.         {
  90.             sb.Append(successor);
  91.             sb.Append(" ");
  92.         }
  93.     }
  94. }
  95. 

  96. public string ReplaceWords2(IList<string> dictionary, string sentence)
  97. {
  98.     var setDictionary = new HashSet<string>(dictionary);
  99.     var successors = sentence.Split();
  100.     for (var i = 0; i < successors.Length; i++)
  101.     {
  102.         var successor = successors[i];
  103.         for (var j = 0; j < successor.Length; j++)
  104.         {
  105.             var subSuccessor = successor.Substring(0, j + 1);
  106.             if (!setDictionary.Contains(subSuccessor)) continue;
  107.             successors[i] = subSuccessor;
  108.             break;
  109.         }
  110.     }
  111. 

  112.     return string.Join(' ', successors);
  113. }
    1. LRU 缓存-mihayou
      请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
      实现 LRUCache 类：
      LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
      int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
      void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
      函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
  1. public class LinkList
  2. {
  3.     public int Value;
  4.     public int Key;
  5.     public LinkList Pre;
  6.     public LinkList Next;
  7. 

  8.     public LinkList(int key, int value)
  9.     {
  10.         Value = value;
  11.         Key = key;
  12.     }
  13. }
  14. 

  15. public class LRUCache
  16. {
  17.     private Dictionary<int, LinkList> __cache = new Dictionary<int, LinkList>();
  18.     private LinkList __head = null;
  19.     private LinkList __tail = null;
  20.     private int __capacity;
  21. 

  22.     public LRUCache(int capacity)
  23.     {
  24.         __capacity = capacity;
  25.         //虚拟头结点以及尾节点
  26.         __head = new LinkList(-1, -1);
  27.         __tail = new LinkList(-1, -1);
  28.         __head.Next = __tail;
  29.         __tail.Pre = __head;
  30.     }
  31. 

  32.     public int Get(int key)
  33.     {
  34.         if (__cache.TryGetValue(key, out var v))
  35.         {
  36.             __Update(v);
  37.             return v.Value;
  38.         }
  39. 

  40.         return -1;
  41.     }
  42. 

  43.     public void Put(int key, int value)
  44.     {
  45.         if (__cache.TryGetValue(key, out var linkList))
  46.         {
  47.             __Update(linkList);
  48.             linkList.Value = value;
  49.         }
  50.         else
  51.         {
  52.             //当容量满的时候，移除最后一个节点
  53.             if (__cache.Count == __capacity)
  54.             {
  55.                 //__tail之前大节点才是真正大尾节点
  56.                 var last = __tail.Pre;
  57.                 __cache.Remove(last.Key);
  58.                 var lastPre = last.Pre;
  59.                 lastPre.Next = __tail;
  60.                 __tail.Pre = lastPre;
  61.             }
  62. 

  63.             //插入新节点，应该插在虚拟头节点的next
  64.             var next = __head.Next;
  65.             linkList = new LinkList(key, value)
  66.             {
  67.                 Next = next,
  68.             };
  69.             next.Pre = linkList;
  70.             linkList.Pre = __head;
  71.             __head.Next = linkList;
  72.         }
  73. 

  74.         __cache[key] = linkList;
  75.     }
  76. 

  77.     private void __Update(LinkList l)
  78.     {
  79.         if (__head.Next == l)
  80.         {
  81.             return;
  82.         }
  83. 

  84.         //先把原先的连接起来
  85.         var pre = l.Pre;
  86.         pre.Next = l.Next;
  87.         l.Next.Pre = pre;
  88. 

  89.         //把l插入header下一个节点
  90.         var headNext = __head.Next;
  91.         headNext.Pre = l;
  92.         l.Pre = __head;
  93.         l.Next = headNext;
  94.         __head.Next = l;
  95.     }
  96. }
  • 460-LFU 缓存
    请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
    实现 LFUCache 类：
    LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
    int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
    void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
    为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
    当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
  1. public class Node
  2. {
  3.     public int Key;
  4.     public int Value;
  5.     public int Cnt;
  6.     public Node Pre;
  7.     public Node Next;
  8. 

  9.     public Node(int key, int value)
  10.     {
  11.         Key = key;
  12.         Value = value;
  13.         Cnt = 0;
  14.     }
  15. }
  16. 

  17. public class LFUCache
  18. {
  19.     private Dictionary<int, Node> __cache = new Dictionary<int, Node>();
  20.     private Node __head;
  21.     private Node __tail;
  22.     private int __capacity;
  23. 

  24.     public LFUCache(int capacity)
  25.     {
  26.         __capacity = capacity;
  27.         __head = new Node(-1, -1);
  28.         __tail = new Node(-1, -1);
  29.         __head.Next = __tail;
  30.         __head.Cnt = Int32.MaxValue;
  31.         __tail.Pre = __head;
  32.         __tail.Cnt = Int32.MinValue;
  33.     }
  34. 

  35.     public int Get(int key)
  36.     {
  37.         if (__cache.TryGetValue(key, out var node))
  38.         {
  39.             __RefreshLinkList(node);
  40.             return node.Value;
  41.         }
  42. 

  43.         return -1;
  44.     }
  45. 

  46.     public void Put(int key, int value)
  47.     {
  48.         if (__capacity == 0)
  49.         {
  50.             return;
  51.         }
  52. 

  53.         if (__cache.TryGetValue(key, out var node))
  54.         {
  55.             node.Value = value;
  56.             __RefreshLinkList(node);
  57.         }
  58.         else
  59.         {
  60.             if (__cache.Count == __capacity)
  61.             {
  62.                 var last = __tail.Pre;
  63.                 last.Pre.Next = __tail;
  64.                 __tail.Pre = last.Pre;
  65.                 __cache.Remove(last.Key);
  66.             }
  67. 

  68.             node = new Node(key, value);
  69.             var temp = __tail.Pre;
  70.             temp.Next = node;
  71.             node.Next = __tail;
  72.             __tail.Pre = node;
  73.             node.Pre = temp;
  74.             __RefreshLinkList(node);
  75.             __cache[key] = node;
  76.         }
  77.     }
  78. 

  79. 

  80.     private void __RefreshLinkList(Node node)
  81.     {
  82.         node.Cnt++;
  83.         if (node.Pre.Cnt > node.Cnt)
  84.         {
  85.             return;
  86.         }
  87. 

  88.         var pre = node.Pre;
  89.         pre.Next = node.Next;
  90.         node.Next.Pre = pre;
  91. 

  92.         pre = __GetNode(pre, node);
  93.         var next = pre.Next;
  94.         node.Next = next;
  95.         pre.Next = node;
  96.         next.Pre = node;
  97.         node.Pre = pre;
  98.     }
  99. 

  100.     private Node __GetNode(Node pre, Node cur)
  101.     {
  102.         var tempHead = __head;
  103.         while (true)
  104.         {
  105.             if (pre.Cnt <= cur.Cnt)
  106.             {
  107.                 pre = pre.Pre;
  108.             }
  109.             else
  110.             {
  111.                 return pre;
  112.             }
  113. 

  114.             if (tempHead.Cnt > cur.Cnt)
  115.             {
  116.                 tempHead = tempHead.Next;
  117.             }
  118.             else
  119.             {
  120.                 return tempHead.Pre;
  121.             }
  122.         }
  123.     }
  124. }

双向链表

  1. public class LFUCache2
  2. {
  3.     class DoubleLinkList
  4.     {
  5.         public int Cnt;
  6.         public Node Head;
  7.         public Node Tail;
  8. 

  9.         public DoubleLinkList(int cnt)
  10.         {
  11.             Head = new Node(-1, -1);
  12.             Tail = new Node(-1, -1);
  13.             Head.Next = Tail;
  14.             Tail.Pre = Head;
  15.             Cnt = cnt;
  16.         }
  17. 

  18.         public void Add(Node node)
  19.         {
  20.             var next = Head.Next;
  21.             node.Next = next;
  22.             Head.Next = node;
  23.             next.Pre = node;
  24.             node.Pre = Head;
  25.         }
  26. 

  27.         public void Remove(Node node)
  28.         {
  29.             var pre = node.Pre;
  30.             pre.Next = node.Next;
  31.             node.Next.Pre = pre;
  32.         }
  33.     }
  34. 

  35.     private Dictionary<int, Node> __cache = new Dictionary<int, Node>();
  36.     private Dictionary<int, DoubleLinkList> __cacheCnt = new Dictionary<int, DoubleLinkList>();
  37.     private int __capacity;
  38.     private int __minCnt;
  39. 

  40.     public LFUCache2(int capacity)
  41.     {
  42.         __capacity = capacity;
  43.         __minCnt = 1;
  44.     }
  45. 

  46.     public int Get(int key)
  47.     {
  48.         if (__capacity == 0)
  49.         {
  50.             return -1;
  51.         }
  52. 

  53.         if (__cache.TryGetValue(key, out var node))
  54.         {
  55.             __UpdateCnt(node);
  56.             return node.Value;
  57.         }
  58. 

  59.         return -1;
  60.     }
  61. 

  62.     public void Put(int key, int value)
  63.     {
  64.         if (__capacity == 0)
  65.         {
  66.             return;
  67.         }
  68. 

  69.         if (__cache.TryGetValue(key, out var node))
  70.         {
  71.             node.Value = value;
  72.             __UpdateCnt(node);
  73.         }
  74.         else
  75.         {
  76.             if (__cache.Count == __capacity)
  77.             {
  78.                 if (__cacheCnt.TryGetValue(__minCnt, out var doubleList) && doubleList.Head.Next != doubleList.Tail)
  79.                 {
  80.                     var t = doubleList.Tail.Pre;
  81.                     __cache.Remove(t.Key);
  82.                     t.Pre.Next = doubleList.Tail;
  83.                     doubleList.Tail.Pre = t.Pre;
  84.                 }
  85.             }
  86. 

  87.             node = new Node(key, value);
  88.             node.Cnt++;
  89.             __InsertNode(node);
  90.             __cache[key] = node;
  91.             __minCnt = 1;
  92.         }
  93.     }
  94. 

  95.     private void __UpdateCnt(Node node)
  96.     {
  97.         if (__cacheCnt.TryGetValue(node.Cnt, out var linkList))
  98.         {
  99.             linkList.Remove(node);
  100.             if (__minCnt == node.Cnt && linkList.Head.Next == linkList.Tail)
  101.             {
  102.                 __minCnt++;
  103.             }
  104.         }
  105. 

  106.         node.Cnt++;
  107.         __InsertNode(node);
  108.     }
  109. 

  110.     private void __InsertNode(Node node)
  111.     {
  112.         if (__cacheCnt.TryGetValue(node.Cnt, out var linkList))
  113.         {
  114.             linkList.Add(node);
  115.         }
  116.         else
  117.         {
  118.             linkList = new DoubleLinkList(node.Cnt);
  119.             linkList.Add(node);
  120.             __cacheCnt[node.Cnt] = linkList;
  121.         }
  122.     }
  123. }
0810学习
0731学习