CED-20240913

今日题目有：

LRU
无重复字符的最长子串

1. LRU

题目描述

请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例：

输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

思路

首先要理解什么是LRU：总是淘汰最近最少使用的。那么我们便需要维护一个类似队列的数据结构，然后同时又要方便查询，O(1)级别的插入和查询。

可以使用哈希表 + 双向链表的方式来实现，双向链表的前向和后向指针可以很方便的实现删除某个自身节点（O(1)级别的插入）。哈希表里是存入的key和对应链表节点，双向链表里存储输入的key-vlaue键值对。这里的key和哈希表里的key是一个key。通过这个key能很快的找到要处理节点（O(1)级别的查询）。双向链表的头部永远存最近操作的节点，尾部则相反，以此来模拟LRU。（模拟队列结构）

那么我们第一个重点就是实现一个双向链表，存储key和value，支持基本的插入节点和删除节点操作。建议使用虚拟节点(Dummy node)来实现，逻辑上更好理解，代码层面也更好实现。

通过哈希表和双向链表我们来进行模拟LRU操作。

put：先判断这个数据在缓存里有没有，即看哈希表里有没有这个key值
- 如果存在，直接把这个节点从原位置移动到表头
- 如果不存在，直接将该节点插入表头然后判断有没有超过LRU的缓存容量，超过的话删除双向链表尾节点，并同时删除哈希表里对应数据
get：同样先判断这个数据缓存里存不存在
- 存在，直接把这个节点从原位置移动到表头，并返回对应数据
- 不存在，return -1

Swift实现

class LRUCache {
    private var capacity:Int
    private var lruCaches = [Int: DoublyLinkedListNode<Int>]()
    private var elementUseList = DoublyLinkedList<Int>()
    
    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    func get(_ key: Int) -> Int {
        if let node = lruCaches[key] {
            // 从原位置移动到表头
            elementUseList.moveToHead(node)
            return node.value
        } else {
            return -1
        }
    }
    
    func put(_ key: Int, _ value: Int) {
        if let node = lruCaches[key] {
            node.value = value
            // 从原位置移动到表头
            elementUseList.moveToHead(node)
        } else {
            let node = DoublyLinkedListNode<Int>(key: key, value: value)
            lruCaches[key] = node
            // 直接插入表头
            elementUseList.insertAtHead(node)
        }
        if lruCaches.count > capacity {
            var tailNode = elementUseList.removedFromTail()
            if let key = tailNode?.key {
                lruCaches.removeValue(forKey: key)
            }
        }
    }
}

public final class DoublyLinkedListNode<T> {
    public var value: T
    public var key: T
    public var next: DoublyLinkedListNode?
    public var preV: DoublyLinkedListNode?
    
    public init(key: T, value: T) {
        self.value = value
        self.key = key
    }
}

public final class DoublyLinkedList<T> {
    private var head: DoublyLinkedListNode<T>?
    private var tail:DoublyLinkedListNode<T>?
    
    var isEmpty: Bool {
        return head == nil
    }
    
    public init() {
        
    }
    
    public func insertAtHead(_ node: DoublyLinkedListNode<T>) {
        node.next = head
        node.preV = nil
        
        if let head = head {
            head.preV = node
        }
        
        head = node
        
        if tail == nil {
            // 如果链表为空，则 tail 也需要指向这个节点
            tail = node
        }
    }
    
    // 从表尾删除
    public func removedFromTail() -> DoublyLinkedListNode<T>? {
        if let tail = tail {
            removeNode(tail)
            return tail
        }
        return nil
    }
    
    public func moveToHead(_ node: DoublyLinkedListNode<T>) {
        removeNode(node)
        insertAtHead(node)
    }
    
    private func removeNode(_ node: DoublyLinkedListNode<T>) {
        let prevNode = node.preV
        let nextNode = node.next
        if let prevNode = prevNode {
            prevNode.next = nextNode
        } else {
            head = nextNode
        }
        
        if let nextNode = nextNode {
            nextNode.preV = prevNode
        } else {
            tail = prevNode
        }
    }
}

2. 无重复字符的最长子串

题目描述

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

示例：
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路

首先因为是找最长”无重复“子串，一个二重循环必然可以暴力解决。但时间复杂度会爆炸，最近试了一次好像已经不能AC了。显然，重复的字符一般出现在一个子串的头尾，可以很容易想到使用“滑动窗口” 或者 “双指针”的技巧来解决。即：不断试探右边界，直到字符串遍历结束 or 出现重复，出现重复时，记录当前最大值。调整左边界到窗口内无重复字符，再重复刚才的操作。然后需要考虑的是，如何判断重复，比较简单的是使用一张哈希表，访问时如果key值存在则表示重复。

Swift实现

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var ans = 0
        let len = s.count
        guard len > 1 else { return len }
        let characters = Array(s)
        var charsIndex = [Character:Int]()
        var startIndex = 0
        for idx in 0..<len {
            let curCharacter = characters[idx]
            if let index = charsIndex[curCharacter] {
                // tips: 新的左边界一定出现在重复字符之后。
                startIndex = max(startIndex, index + 1)
            }
            charsIndex[curCharacter] = idx
            ans = max(ans, idx - startIndex + 1)
        }
        return ans
    }
}

1. LRU#

题目描述#

思路#

Swift实现#

2. 无重复字符的最长子串#

题目描述#

思路#

Swift实现#

1. LRU

题目描述

思路

Swift实现

2. 无重复字符的最长子串

题目描述

思路

Swift实现