Python 刷题清单¶

import heapq

heap = []
heapq.heappush(heap, val)          # 入堆 O(logn)
heapq.heappop(heap)                # 弹出最小值 O(logn)
heap[0]                            # 查看堆顶（最小值）O(1)

# 最大堆：存入负值
heapq.heappush(heap, -val)
-heapq.heappop(heap)

# 自定义排序：使用元组，按第一个元素排序
heapq.heappush(heap, (priority, index, value))

# 从列表建堆 O(n)
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)

# 前 K 个最小/最大元素
heapq.nsmallest(k, nums)
heapq.nlargest(k, nums)

from collections import deque, defaultdict, Counter

# deque: 双端队列，两端操作均为 O(1)
q = deque()
q = deque([1, 2, 3])
q.append(x)                        # 右端入队
q.appendleft(x)                    # 左端入队
q.pop()                            # 右端出队
q.popleft()                        # 左端出队（list.pop(0) 是 O(n)）

# defaultdict: 带默认值的字典
d = defaultdict(int)               # 默认值 0
d = defaultdict(list)              # 默认值 []
d[key] += 1                        # 无需判断 key 是否存在

# Counter: 计数器
cnt = Counter("aabbc")             # {'a': 2, 'b': 2, 'c': 1}
cnt = Counter(nums)
cnt.most_common(k)                 # 前 k 个高频元素

from functools import cache, lru_cache

# @cache: 自动缓存递归结果（Python 3.9+）
@cache
def dfs(i, j):
    if i == 0:
        return 0
    return min(dfs(i-1, j), dfs(i, j-1)) + grid[i][j]

# @lru_cache: 带容量限制的缓存（Python 3.2+）
@lru_cache(maxsize=None)           # None 表示无限缓存
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

# 注意：参数必须是可哈希类型（不能传 list，可以传 tuple）

import bisect

# 在有序列表中查找插入位置
bisect.bisect_left(nums, target)   # 第一个 >= target 的位置
bisect.bisect_right(nums, target)  # 第一个 > target 的位置

# 插入并保持有序
bisect.insort(nums, val)

from itertools import accumulate, combinations, permutations

# 前缀和
list(accumulate(nums))             # [1, 3, 6, 10]（输入 [1,2,3,4]）

# 组合与排列
list(combinations([1,2,3], 2))     # [(1,2), (1,3), (2,3)]
list(permutations([1,2,3], 2))     # [(1,2), (1,3), (2,1), ...]

# Time: O(n), Space: O(n)
def subarraySum(nums: list[int], k: int) -> int:
    count, prefix_sum = 0, 0
    prefix_sum_map = {0: 1}  # 兼容 nums=[3], k=3
    for num in nums:
        prefix_sum += num  # 计算前缀和
        if prefix_sum - k in prefix_sum_map:  # 查找是否存在
            count += prefix_sum_map[prefix_sum - k]  # 累计频率
        prefix_sum_map[prefix_sum] = prefix_sum_map.get(prefix_sum, 0) + 1  # 对前缀和值的出现次数统计

    return count

# Time: O(n), Space: O(n)
def twoSum(nums: list[int], target: int) -> list[int]:
    # 哈希表记录出现的元素及索引
    # 遍历 nums，如果 target - num 在哈希表中，返回索引
    # 否则将 num 加入哈希表

    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [i, seen[target - num]]
        seen[num] = i

    return []

# Time: O(n), Space: O(n)
def longestConsecutive(nums: list[int]) -> int:
    has = set(nums)  # 使用Python特有的集合简化判断

    ans = 0
    for num in has:
        if num - 1 in has:  # 上一个数存在于集合，说明 num 不是序列的起点
            continue

        next_num = num + 1
        while next_num in has:  # 不断查找下一个序列是否在集合中
            next_num += 1

        ans = max(ans, next_num - num)

    return ans

# 排序解法
# Time: O(m*nlogn), Space: O(m*n)
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        key = "".join(sorted(s))
        groups.setdefault(key, []).append(s)

    return list(groups.values())

# 计数解法
# Time: O(m*n), Space: O(m*n)
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)  # 列表不可哈希，转为元组作为键
        groups.setdefault(key, []).append(s)

    return list(groups.values())

# Time: O(n), Space: O(1)
def maxArea(height: list[int]) -> int:
    max_area, left, right = 0, 0, len(height) - 1
    while left < right:
        area = (right - left) * min(height[left], height[right])  # 以较矮的作为高计算面积
        max_area = max(max_area, area)
        # 只移动较矮的一边
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

# Time: O(n), Space: O(1)
def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0  # 分别代表左侧和右侧已扫描区域最高的柱子
    water = 0
    while left < right:
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        # 移动较矮的一边，并累加该处的水量
        if height[left] < height[right]:
            water += left_max - height[left]
            left += 1
        else:
            water += right_max - height[right]
            right -= 1

    return water

# Time: O(m+n), Space: O(1)
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1, p2, tail = m - 1, n - 1, len(nums1) - 1

    # 只需检查 p2 >= 0，因为 nums2 处理完后，nums1 剩余元素已在正确位置
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

# Time: O(n), Space: O(1)
def moveZeroes(nums: list[int]) -> None:
    slow = 0  # 并不能确定 nums[0] 是否为非零值
    for fast in range(len(nums)):  # fast 要从0开始遍历，否则可能遗漏首位的零值交换。首位是非零值会发生自己和自己交换
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

# Time: O(n), Space: O(1)
def removeDuplicates(nums: list[int]) -> int:
    slow = 0
    for fast in range(1, len(nums)):
        if nums[slow] != nums[fast]:
            slow += 1  # 注意要交换到 slow 的下一个位置
            nums[slow] = nums[fast]

    return slow + 1  # 注意差1问题

# Time: O(n), Space: O(n)
def lengthOfLongestSubstring(self, s: str) -> int:
    ans = left = 0
    window = set()  # 维护从下标 left 到下标 right 的字符
    for right, c in enumerate(s):
        # 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
        # 所以要在加入 c 之前，先移出窗口内的 c
        while c in window:  # 窗口内有 c
            window.remove(s[left])
            left += 1  # 缩小窗口
        window.add(c)  # 加入 c
        ans = max(ans, right - left + 1)  # 更新窗口长度最大值
    return ans

# Time: O(n), Space: O(n)
def lengthOfLongestSubstring(self, s: str) -> int:
    ans = left = 0
    last_seen = {}  # 记录字符 c 上一次出现的下标

    for right, c in enumerate(s):
        if c in last_seen:
            # 核心逻辑：防止指针回退
            # 如果 c 上一次出现的位置在 left 左侧，left 保持不变；如果在 right 窗口内，left 直接跳跃
            left = max(left, last_seen[c] + 1)

        last_seen[c] = right  # 更新字符 c 的最新下标
        ans = max(ans, right - left + 1)  # 更新最大长度

    return ans

# Time: O(n²), Space: O(1)
def threeSum(nums: list[int]) -> list[list[int]]:
    if len(nums) < 3:
        return []

    nums.sort()

    ans = []
    # 先固定第一个数
    for i in range(len(nums) - 2):
        # 提前剪枝：如果排序后第一个数已经大于0，后面都是正数，不可能和为0
        if nums[i] > 0:
            break

        # 对第1个数去重
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 用双指针让剩余两数之和与第一个数的和为0
        l, r = i + 1, len(nums) - 1
        while l < r:
            sum = nums[i] + nums[l] + nums[r]
            if sum < 0:  # 和太小，需要右移靠近较大数
                l += 1
            elif sum > 0:  # 和太大，需要左移靠近较小数
                r -= 1
            else:  # 和为 0
                ans.append([nums[i], nums[l], nums[r]])

                # 对第2、3个数去重
                l_val, r_val = nums[l], nums[r]
                while l < r and nums[l] == l_val:
                    l += 1
                while l < r and nums[r] == r_val:
                    r -= 1

    return ans

# Time: O(n²), Space: O(1)
def longestPalindrome(s: str) -> str:
    start, max_len = 0, 0

    # 从中心向两侧扩展，返回回文长度
    def expand(l: int, r: int) -> None:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1

        # 此时 [l+1, r-1] 是回文，注意while中的l和r已经越界，因此下方要-1
        nonlocal start, max_len
        if r - l - 1 > max_len:
            start = l + 1
            max_len = r - l - 1

    for i in range(len(s)):
        # 无法预知以某个位置为中心的最长回文是奇数还是偶数长度，因此需要同时遍历两种情况，取最长的那个
        expand(i, i)      # 奇数长度回文（如 "aba"）
        expand(i, i + 1)  # 偶数长度回文（如 "abba"）

    return s[start:start + max_len]

# Time: O(n), Space: O(1)
def nextPermutation(nums: list[int]) -> None:
    # 从右往左找到第一个下降点 i
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # 从右往左找到第一个大于 nums[i] 的数 j
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 交换 i 和 j
        nums[i], nums[j] = nums[j], nums[i]

    # 反转 i 之后的部分
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

# Time: O(n+m), Space: O(1)
def compareVersion(version1: str, version2: str) -> int:
    n, m = len(version1), len(version2)
    i, j = 0, 0
    while i < n or j < m:
        x = 0
        while i < n and version1[i] != '.':
            x = x * 10 + int(version1[i])
            i += 1
        i += 1  # 跳过点号

        y = 0
        while j < m and version2[j] != '.':
            y = y * 10 + int(version2[j])
            j += 1
        j += 1  # 跳过点号

        if x > y:
            return 1
        if x < y:
            return -1

    return 0

# Time: O(n), Space: O(1)
def reverseList(head: ListNode) -> ListNode:
    prev = None
    # 暂存、反转、移动
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt

    return prev

# Time: O(n), Space: O(1)
def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    dummy = ListNode(next=head)  # 可能从头结点开始反转

    prev = dummy
    for _ in range(1, left):
        prev = prev.next

    curr = prev.next
    for _ in range(left, right):  # 这段代码画个步骤图就出来了
        nxt = curr.next      # 暂存操作节点的移动路径
        curr.next = nxt.next # 摘下节点
        nxt.next = prev.next # 插到区间头部
        prev.next = nxt      # 移动操作的节点

    return dummy.next

# Time: O(n), Space: O(1)
def middleNode(head: ListNode) -> ListNode:
    if not head:
        return None

    slow, fast = head, head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next

    return slow

# Time: O(n), Space: O(1)
def hasCycle(head: ListNode) -> bool:
    slow, fast = head, head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            return True

    return False

# Time: O(n), Space: O(n)
def detectCycle(head: ListNode) -> ListNode:
    seen = set()
    while head:
        if head in seen:
            return head
        seen.add(head)
        head = head.next

    return None

# Time: O(m+n), Space: O(1)
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    pA, pB = headA, headB
    while pA != pB:
        pA = headB if pA is None else pA.next
        pB = headA if pB is None else pB.next

    return pA  # 没有相交时，遍历结束的链表最终指向 None

# Time: O(m+n), Space: O(1)
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    current = dummy

    # 注意该遍历需同时操作3个链表
    while l1 and l2:  # 注意是 and
        if l1.val < l2.val:      # 将较小的值挂载在新链表上
            current.next = l1
            l1 = l1.next         # 移动原链表
        else:
            current.next = l2
            l2 = l2.next
        current = current.next   # 移动新链表

    # 将链表剩余部分挂载，同时处理原链表为空
    current.next = l1 if l1 else l2

    # 注意返回的是 dummy.next
    return dummy.next

def deleteDuplicates(head: ListNode) -> ListNode:
    curr = head
    while curr and curr.next:
        if curr.val == curr.next.val:
            curr.next = curr.next.next
        else:
            curr = curr.next

    return head

# Time: O(n), Space: O(1)
def reverseKGroup(head: ListNode, k: int) -> ListNode:
    dummy = ListNode(next=head)
    prev = dummy

    while True:
        tail = prev
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next  # 不足 k 个时结束反转

        next_group = tail.next  # 下一组起始位置

        # 头插法局部反转链表
        curr = prev.next
        for _ in range(k - 1):
            nxt = curr.next
            curr.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt

        # 区间反转完成后，准备下一组的反转，此时 curr 移动到了区间末尾
        curr.next = next_group
        prev = curr

# 归并解法
# Time: O(n·logk), Space: O(logk)
def mergeKLists(lists: list[ListNode]) -> ListNode:
    if not lists:
        return None

    return merge_range(lists, 0, len(lists) - 1)

def merge_range(lists: list[ListNode], left: int, right: int) -> ListNode:
    if left == right:
        return lists[left]

    mid = left + (right - left) // 2
    l1 = merge_range(lists, left, mid)
    l2 = merge_range(lists, mid + 1, right)

    return merge_two_lists(l1, l2)

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    curr.next = l1 if l1 else l2

    return dummy.next

# 最小堆
# Time: O(nlogk), Space: O(k)
import heapq

def mergeKLists(lists: list[ListNode]) -> ListNode:
    heap = []
    # 把每个链表的头结点放入小顶堆
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    curr = dummy

    # 从堆中弹出节点，并挂载到新的链表
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next

        # 把链表的下一个节点放入堆中
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

# Time: O(n·logn), Space: O(logn)
def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    mid = split(head)
    left = sortList(head)
    right = sortList(mid)

    return merge_two_lists(left, right)

def split(head: ListNode) -> ListNode:
    prev, slow, fast = head, head, head
    while fast and fast.next:
        prev, slow, fast = slow, slow.next, fast.next.next

    prev.next = None  # 注意需要切断链表

    return slow

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    if l1:
        curr.next = l1
    if l2:
        curr.next = l2

    return dummy.next

# Time: O(n), Space: O(1)
def reorderList(head: ListNode) -> None:
    # 找中点
    mid = middle(head)

    # 断开链表
    l1 = head
    l2 = mid.next
    mid.next = None

    # 反转后半部分
    l2 = reverse(l2)

    # 合并链表
    merge(l1, l2)

def middle(head: ListNode) -> ListNode:
    slow = fast = head
    # 由于找到中点后要断开，因此 slow 要停在中点的前一个节点，要用 fast.next 和 fast.next.next
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next

    return slow

def reverse(head: ListNode) -> ListNode:
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt

    return prev

def merge(l1: ListNode, l2: ListNode) -> None:
    while l1 and l2:
        l1_next = l1.next
        l2_next = l2.next

        l1.next = l2
        l1 = l1_next

        l2.next = l1
        l2 = l2_next

# Time: O(n), Space: O(1)
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    curr = dummy

    while curr.next and curr.next.next:
        # 取出第一个节点的值作为基准，比较后边是否存在连续重复的值
        val = curr.next.val
        # 下一个与下下个节点值相同，说明存在重复
        if val == curr.next.next.val:
            # 不断取下一个节点与第一个节点比较，相同则删除
            while curr.next and curr.next.val == val:
                curr.next = curr.next.next
        else:
            curr = curr.next

    return dummy.next