0801学习

agile Posted on Aug 1 2023

面试 leetcode学习

-   648. 单词替换-字节
在英语中，我们有一个叫做 词根(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"

---

```C#
public class PreWords
{
    public char Char;
    public bool IsWord;
    public Dictionary<char, PreWords> Next = new Dictionary<char, PreWords>();

public PreWords(char c, bool isWord)
    {
        Char = c;
        IsWord = isWord;
    }
}

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

public string ReplaceWords(IList<string> dictionary, string sentence)
{
    foreach (var str in dictionary)
    {
        var first = str[0];
        if (!__dictionary.TryGetValue(first, out var p))
        {
            p = new PreWords(first, false);
            __dictionary[first] = p;
        }

for (int j = 0; j < str.Length;)
        {
            if (j == str.Length - 1)
            {
                p.IsWord = true;
                break;
            }

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

p = next;
        }
    }

var successores = sentence.Split();
    var sb = new StringBuilder();
    foreach (var successor in successores)
    {
        __ReplaceStr(successor, sb);
    }

sb.Remove(sb.Length - 1, 1);
    return sb.ToString();
}

private void __ReplaceStr(string successor, StringBuilder sb)
{
    if (successor.Length > 0)
    {
        var first = successor[0];
        if (__dictionary.TryGetValue(first, out var p))
        {
            if (p.IsWord)
            {
                sb.Append(first);
                sb.Append(" ");
            }
            else
            {
                var index = 1;
                var find = false;
                for (; index < successor.Length; index++)
                {
                    if (p.Next.TryGetValue(successor[index], out var next))
                    {
                        p = next;
                        if (!p.IsWord) continue;
                        find = true;
                    }

break;
                }

sb.Append(find ? successor.Substring(0, index + 1) : successor);
                sb.Append(" ");
            }
        }
        else
        {
            sb.Append(successor);
            sb.Append(" ");
        }
    }
}

public string ReplaceWords2(IList<string> dictionary, string sentence)
{
    var setDictionary = new HashSet<string>(dictionary);
    var successors = sentence.Split();
    for (var i = 0; i < successors.Length; i++)
    {
        var successor = successors[i];
        for (var j = 0; j < successor.Length; j++)
        {
            var subSuccessor = successor.Substring(0, j + 1);
            if (!setDictionary.Contains(subSuccessor)) continue;
            successors[i] = subSuccessor;
            break;
        }
    }

return string.Join(' ', successors);
}
```

---

-   146. 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) 的平均时间复杂度运行。

---

```C#
public class LinkList
{
    public int Value;
    public int Key;
    public LinkList Pre;
    public LinkList Next;

public LinkList(int key, int value)
    {
        Value = value;
        Key = key;
    }
}

public class LRUCache
{
    private Dictionary<int, LinkList> __cache = new Dictionary<int, LinkList>();
    private LinkList __head = null;
    private LinkList __tail = null;
    private int __capacity;

public LRUCache(int capacity)
    {
        __capacity = capacity;
        //虚拟头结点以及尾节点
        __head = new LinkList(-1, -1);
        __tail = new LinkList(-1, -1);
        __head.Next = __tail;
        __tail.Pre = __head;
    }

public int Get(int key)
    {
        if (__cache.TryGetValue(key, out var v))
        {
            __Update(v);
            return v.Value;
        }

return -1;
    }

public void Put(int key, int value)
    {
        if (__cache.TryGetValue(key, out var linkList))
        {
            __Update(linkList);
            linkList.Value = value;
        }
        else
        {
            //当容量满的时候，移除最后一个节点
            if (__cache.Count == __capacity)
            {
                //__tail之前大节点才是真正大尾节点
                var last = __tail.Pre;
                __cache.Remove(last.Key);
                var lastPre = last.Pre;
                lastPre.Next = __tail;
                __tail.Pre = lastPre;
            }

//插入新节点，应该插在虚拟头节点的next
            var next = __head.Next;
            linkList = new LinkList(key, value)
            {
                Next = next,
            };
            next.Pre = linkList;
            linkList.Pre = __head;
            __head.Next = linkList;
        }

__cache[key] = linkList;
    }

private void __Update(LinkList l)
    {
        if (__head.Next == l)
        {
            return;
        }

//先把原先的连接起来
        var pre = l.Pre;
        pre.Next = l.Next;
        l.Next.Pre = pre;

//把l插入header下一个节点
        var headNext = __head.Next;
        headNext.Pre = l;
        l.Pre = __head;
        l.Next = headNext;
        __head.Next = l;
    }
}
```

-   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) 的平均时间复杂度运行。

---

```C#
public class Node
{
    public int Key;
    public int Value;
    public int Cnt;
    public Node Pre;
    public Node Next;

public Node(int key, int value)
    {
        Key = key;
        Value = value;
        Cnt = 0;
    }
}

public class LFUCache
{
    private Dictionary<int, Node> __cache = new Dictionary<int, Node>();
    private Node __head;
    private Node __tail;
    private int __capacity;

public LFUCache(int capacity)
    {
        __capacity = capacity;
        __head = new Node(-1, -1);
        __tail = new Node(-1, -1);
        __head.Next = __tail;
        __head.Cnt = Int32.MaxValue;
        __tail.Pre = __head;
        __tail.Cnt = Int32.MinValue;
    }

public int Get(int key)
    {
        if (__cache.TryGetValue(key, out var node))
        {
            __RefreshLinkList(node);
            return node.Value;
        }

return -1;
    }

public void Put(int key, int value)
    {
        if (__capacity == 0)
        {
            return;
        }

if (__cache.TryGetValue(key, out var node))
        {
            node.Value = value;
            __RefreshLinkList(node);
        }
        else
        {
            if (__cache.Count == __capacity)
            {
                var last = __tail.Pre;
                last.Pre.Next = __tail;
                __tail.Pre = last.Pre;
                __cache.Remove(last.Key);
            }

node = new Node(key, value);
            var temp = __tail.Pre;
            temp.Next = node;
            node.Next = __tail;
            __tail.Pre = node;
            node.Pre = temp;
            __RefreshLinkList(node);
            __cache[key] = node;
        }
    }

private void __RefreshLinkList(Node node)
    {
        node.Cnt++;
        if (node.Pre.Cnt > node.Cnt)
        {
            return;
        }

var pre = node.Pre;
        pre.Next = node.Next;
        node.Next.Pre = pre;

pre = __GetNode(pre, node);
        var next = pre.Next;
        node.Next = next;
        pre.Next = node;
        next.Pre = node;
        node.Pre = pre;
    }

private Node __GetNode(Node pre, Node cur)
    {
        var tempHead = __head;
        while (true)
        {
            if (pre.Cnt <= cur.Cnt)
            {
                pre = pre.Pre;
            }
            else
            {
                return pre;
            }

if (tempHead.Cnt > cur.Cnt)
            {
                tempHead = tempHead.Next;
            }
            else
            {
                return tempHead.Pre;
            }
        }
    }
}
```

---

双向链表

```C#
public class LFUCache2
{
    class DoubleLinkList
    {
        public int Cnt;
        public Node Head;
        public Node Tail;

public DoubleLinkList(int cnt)
        {
            Head = new Node(-1, -1);
            Tail = new Node(-1, -1);
            Head.Next = Tail;
            Tail.Pre = Head;
            Cnt = cnt;
        }

public void Add(Node node)
        {
            var next = Head.Next;
            node.Next = next;
            Head.Next = node;
            next.Pre = node;
            node.Pre = Head;
        }

public void Remove(Node node)
        {
            var pre = node.Pre;
            pre.Next = node.Next;
            node.Next.Pre = pre;
        }
    }

private Dictionary<int, Node> __cache = new Dictionary<int, Node>();
    private Dictionary<int, DoubleLinkList> __cacheCnt = new Dictionary<int, DoubleLinkList>();
    private int __capacity;
    private int __minCnt;

public LFUCache2(int capacity)
    {
        __capacity = capacity;
        __minCnt = 1;
    }

public int Get(int key)
    {
        if (__capacity == 0)
        {
            return -1;
        }

if (__cache.TryGetValue(key, out var node))
        {
            __UpdateCnt(node);
            return node.Value;
        }

return -1;
    }

public void Put(int key, int value)
    {
        if (__capacity == 0)
        {
            return;
        }

if (__cache.TryGetValue(key, out var node))
        {
            node.Value = value;
            __UpdateCnt(node);
        }
        else
        {
            if (__cache.Count == __capacity)
            {
                if (__cacheCnt.TryGetValue(__minCnt, out var doubleList) && doubleList.Head.Next != doubleList.Tail)
                {
                    var t = doubleList.Tail.Pre;
                    __cache.Remove(t.Key);
                    t.Pre.Next = doubleList.Tail;
                    doubleList.Tail.Pre = t.Pre;
                }
            }

node = new Node(key, value);
            node.Cnt++;
            __InsertNode(node);
            __cache[key] = node;
            __minCnt = 1;
        }
    }

private void __UpdateCnt(Node node)
    {
        if (__cacheCnt.TryGetValue(node.Cnt, out var linkList))
        {
            linkList.Remove(node);
            if (__minCnt == node.Cnt && linkList.Head.Next == linkList.Tail)
            {
                __minCnt++;
            }
        }

node.Cnt++;
        __InsertNode(node);
    }

private void __InsertNode(Node node)
    {
        if (__cacheCnt.TryGetValue(node.Cnt, out var linkList))
        {
            linkList.Add(node);
        }
        else
        {
            linkList = new DoubleLinkList(node.Cnt);
            linkList.Add(node);
            __cacheCnt[node.Cnt] = linkList;
        }
    }
}
```