Studying-CodeTop | 3. 无重复字符的最长子串、206. 反转链表、146. LRU 缓存

这三个问题都涉及到字符串和链表的操作，下面我将分别给出Python语言的解决方案。

1. 无重复字符的最长子串：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 使用一个哈希集合记录字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为-1，代表字符串为空
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 当前无重复字符的长度
            ans = max(ans, rk - i + 1)
        return ans

2. 反转链表：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 前一个节点
        prev = None
        # 当前节点
        curr = head
        while curr is not None:
            # 下一个节点
            next_node = curr.next
            # 将当前节点指向前一个节点
            curr.next = prev
            # 前一个节点和当前节点都向后移动一位
            prev = curr
            curr = next_node
        return prev

3. LRU 缓存机制：

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.size = 0
        self.head = None
        self.tail = None
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value
 
    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = Node(key, value)
            self.cache[key] = node
            if self.size == self.capacity:
                removed = self.removeTail()
                del self.cache[removed.key]
            self.moveToHead(node)
            self.size += 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
 
    def moveToHead(self, node):
        if self.head is None:
            self.head = node
            self.tail = node
            return
        if node is self.head:
            return
        node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
        if node is