905 字
5 分钟
3月21日刷题笔记
本篇题目
#3无重复字符的最长子串
Medium
#438找到字符串中所有字母异位词
Medium
#206反转链表
Easy
#141环形链表
Easy
#146LRU 缓存机制
Medium
一、滑动窗口
适用场景：子串 / 子数组问题，要求连续，窗口内维护某种状态
万能模板：
window = set() # 记录窗口内的元素l = 0
for r in range(len(s)): # 1. 窗口不合法就收缩左边 while 窗口不合法: window.remove(s[l]) l += 1
# 2. 右边扩张，加入新元素 window.add(s[r])
# 3. 更新答案 update(result)1. 无重复字符的最长子串
#3无重复字符的最长子串
Medium
- 要点：窗口内不能有重复字符，有重复就移动 left 直到合法
- 答案：每轮更新
max(result, right - left + 1)
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: window = set() max_len = 0 l = 0
for r in range(len(s)): while s[r] in window: # 有重复就收缩左边 window.remove(s[l]) l += 1
window.add(s[r]) max_len = max(max_len, r - l + 1)
return max_len438. 找到字符串中所有字母异位词
#438找到字符串中所有字母异位词
Medium
- 要点：固定窗口大小 =
len(p)，每个窗口排序后和p比较 - 复杂度：O(m·n·log n)，每个窗口都排序，数据量大时较慢
- 优化方向：改用 Counter 或频次数组比较，可降到 O(m)
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: p = sorted(p) m, n = len(s), len(p) ans = []
if m < n: return ans
for i in range(m - n + 1): if sorted(s[i: i+n]) == p: # 每个窗口排序比较 ans.append(i)
return ans二、链表
IMPORTANT链表题核心：画图！搞清楚指针指向再写代码
动手写代码前先在纸上或脑子里把每个指针的变化画清楚，否则极容易断链或死循环。
链表题核心：画图！搞清楚指针指向再写代码
206. 反转链表
#206反转链表
Easy
- 要点：双指针，
prev和curr同向前进，每步反转箭头方向
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head prev = None
while curr: next_node = curr.next # 先保存下一个，防止断链 curr.next = prev # 反转箭头 prev = curr # prev 前进 curr = next_node # curr 前进 return prev141. 环形链表
#141环形链表
Easy
- 要点：快慢指针，slow 走1步，fast 走2步，相遇说明有环
class Solution: def hasCycle(head): slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False146. LRU 缓存机制
#146LRU 缓存机制
Medium
- 要点：哈希表（O(1)查找）+ 双向链表（O(1)维护顺序）
- 技巧：用 Python
OrderedDict可以一行搞定顺序维护，下面是手写 Node 的实现
class Node: # key=0,val=0 代表创建节点且不传参时候的默认值 Node() def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None
class LRUCache:
def __init__(self, capacity: int): self.cap = capacity self.cache = {} # key → node 的映射，用来 O(1) 查找节点 self.head = Node() # 哨兵头节点，不存真实数据 self.tail = Node() # 哨兵尾节点，不存真实数据 self.head.next = self.tail self.tail.prev = self.head
def remove(self, node): node.prev.next = node.next node.next.prev = node.prev
def add_to_head(self, node): node.next = self.head.next # ① node 的 next 指向原来的第一个节点 node.prev = self.head # ② node 的 prev 指向 head self.head.next.prev = node # ③ 原来第一个节点的 prev 指向 node self.head.next = node # ④ head 的 next 指向 node
def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self.remove(node) self.add_to_head(node) return node.val
def put(self, key: int, value: int) -> None: if key in self.cache: self.remove(self.cache[key]) del self.cache[key]
node = Node(key, value) self.cache[key] = node self.add_to_head(node) if len(self.cache) > self.cap: lru = self.tail.prev self.remove(lru) # 注意用的是 lru.key 而不是 key——key 是刚插入的新节点，lru.key 才是被淘汰节点的键 del self.cache[lru.key]
# Your LRUCache object will be instantiated and called as such:# obj = LRUCache(capacity)# param_1 = obj.get(key)# obj.put(key,value)NOTEremove() 实现细节
node自身的prev/next不需要清空，因为后续调用add_to_head()时会重新设置这两个指针。
CAUTIONLRU 淘汰时的易错点
del self.cache[lru.key]用的是lru.key（被淘汰节点的键），而不是key（刚插入的新节点的键），两者不要混淆。