秋招算法：
从题意到模板，从代码到表达。

def three_sum(nums):
    a = sorted(nums)
    ans = []
    for i in range(len(a) - 2):
        if i > 0 and a[i] == a[i - 1]:
            continue
        if a[i] > 0:
            break
        left, right = i + 1, len(a) - 1
        while left < right:
            total = a[i] + a[left] + a[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                ans.append([a[i], a[left], a[right]])
                left += 1
                right -= 1
                while left < right and a[left] == a[left - 1]:
                    left += 1
                while left < right and a[right] == a[right + 1]:
                    right -= 1
    return ans

def remove_value(nums, target):
    write = 0
    for read in range(len(nums)):
        if nums[read] != target:
            nums[write] = nums[read]
            write += 1
    return write  # 只有 nums[:write] 有效

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

def trap_water(height):
    left, right = 0, len(height) - 1
    left_max = right_max = ans = 0
    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, height[left])
            ans += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            ans += right_max - height[right]
            right -= 1
    return ans

def sort_colors(nums):
    low = cur = 0
    high = len(nums) - 1
    # [0,low) 为0；[low,cur) 为1；[cur,high] 未知
    while cur <= high:
        if nums[cur] == 0:
            nums[low], nums[cur] = nums[cur], nums[low]
            low += 1
            cur += 1
        elif nums[cur] == 2:
            nums[cur], nums[high] = nums[high], nums[cur]
            high -= 1  # 换来的数还未检查
        else:
            cur += 1

def kmp_find(text, pattern):
    if not pattern:
        return 0
    pi = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    j = 0
    for i, ch in enumerate(text):
        while j and ch != pattern[j]:
            j = pi[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1

from collections import Counter, defaultdict

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

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        groups[''.join(sorted(word))].append(word)
    return list(groups.values())

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:
            end = x
            while end in values:
                end += 1
            best = max(best, end - x)
    return best

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i, x in enumerate(nums):
        if x != i + 1:
            return i + 1
    return n + 1

def single_number(nums):  # 其余每个值恰好出现两次
    value = 0
    for x in nums:
        value ^= x
    return value

def majority_element(nums):  # 保证非空且存在 > n/2 的元素
    candidate = None
    votes = 0
    for x in nums:
        if votes == 0:
            candidate = x
        votes += 1 if x == candidate else -1
    return candidate

def longest_unique(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        left = max(left, last.get(ch, -1) + 1)
        last[ch] = right
        best = max(best, right - left + 1)
    return best

from collections import Counter, defaultdict

def min_window(s, t):
    if not t:
        return ''
    need = Counter(t)
    have = defaultdict(int)
    formed = left = 0
    best_len, best_left = float('inf'), 0
    for right, ch in enumerate(s):
        if ch in need:
            have[ch] += 1
            if have[ch] == need[ch]:
                formed += 1
        while formed == len(need):
            if right - left + 1 < best_len:
                best_len, best_left = right - left + 1, left
            old = s[left]
            if old in need:
                if have[old] == need[old]:
                    formed -= 1
                have[old] -= 1
            left += 1
    return '' if best_len == float('inf') else s[best_left:best_left+best_len]

def find_anagrams(s, p):
    if not p or len(p) > len(s):
        return []
    need, window = [0] * 26, [0] * 26
    for ch in p:
        need[ord(ch) - ord('a')] += 1
    ans, k = [], len(p)
    for i, ch in enumerate(s):
        window[ord(ch) - ord('a')] += 1
        if i >= k:
            window[ord(s[i-k]) - ord('a')] -= 1
        if i >= k - 1 and window == need:
            ans.append(i - k + 1)
    return ans

def first_true(lo, hi, check):
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def lower_bound(nums, target):
    return first_true(0, len(nums), lambda i: nums[i] >= target)

def upper_bound(nums, target):
    return first_true(0, len(nums), lambda i: nums[i] > target)

def equal_range(nums, target):
    left, right = lower_bound(nums, target), upper_bound(nums, target)
    return [-1, -1] if left == right else [left, right - 1]

def integer_sqrt(x):  # x >= 0
    return first_true(0, x + 1, lambda v: v * v > x) - 1

def rotated_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

def rotated_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

def median_two_sorted(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        al = a[i-1] if i else -float('inf')
        ar = a[i] if i < m else float('inf')
        bl = b[j-1] if j else -float('inf')
        br = b[j] if j < n else float('inf')
        if al <= br and bl <= ar:
            if (m + n) % 2:
                return max(al, bl)
            return (max(al, bl) + min(ar, br)) / 2
        if al > br:
            hi = i - 1
        else:
            lo = i + 1
    raise ValueError('输入必须有序且总长度非零')

def build_prefix(nums):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    return prefix

def subarray_sum_k(nums, k):
    freq = {0: 1}
    total = ans = 0
    for x in nums:
        total += x
        ans += freq.get(total - k, 0)  # 先查询
        freq[total] = freq.get(total, 0) + 1  # 再登记
    return ans

def min_positive_length(nums, target):
    left = total = 0
    best = len(nums) + 1
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best > len(nums) else best

def product_except_self(nums):
    ans = [1] * len(nums)
    product = 1
    for i, x in enumerate(nums):
        ans[i] = product
        product *= x
    product = 1
    for i in range(len(nums)-1, -1, -1):
        ans[i] *= product
        product *= nums[i]
    return ans

def stock_once(prices):
    low, best = float('inf'), 0
    for price in prices:
        best = max(best, price - low)
        low = min(low, price)
    return best

def stock_unlimited(prices):
    return sum(max(0, prices[i] - prices[i-1])
               for i in range(1, len(prices)))

def can_jump(nums):
    far = 0
    for i, step in enumerate(nums):
        if i > far:
            return False
        far = max(far, i + step)
    return True

def min_jumps(nums):
    end = far = jumps = 0
    for i in range(len(nums)-1):
        if i > far:
            return -1
        far = max(far, i + nums[i])
        if i == end:
            if far == end:
                return -1
            jumps += 1
            end = far
    return jumps

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    start = end = 0
    ans = []
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            ans.append(end - start + 1)
            start = i + 1
    return ans

def valid_brackets(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            return False
    return not stack

class MinStack:
    def __init__(self):
        self.stack = []
    def push(self, x):
        low = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, low))
    def pop(self):
        return self.stack.pop()[0]
    def top(self):
        return self.stack[-1][0]
    def getMin(self):
        return self.stack[-1][1]

def decode_string(s):
    stack, cur, number = [], '', 0
    for ch in s:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == '[':
            stack.append((cur, number))
            cur, number = '', 0
        elif ch == ']':
            prefix, times = stack.pop()
            cur = prefix + cur * times
        else:
            cur += ch
    return cur

def daily_temperatures(temperatures):
    ans = [0] * len(temperatures)
    stack = []
    for i, value in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < value:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

def largest_rectangle(heights):
    a = heights + [0]
    stack = [-1]
    best = 0
    for i, value in enumerate(a):
        while stack[-1] != -1 and a[stack[-1]] > value:
            h = a[stack.pop()]
            best = max(best, h * (i - stack[-1] - 1))
        stack.append(i)
    return best

def longest_valid_parentheses(s):
    stack, best = [-1], 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # 最近非法右括号边界
            else:
                best = max(best, i - stack[-1])
    return best

from collections import deque

def sliding_max(nums, k):
    queue, ans = deque(), []
    for i, value in enumerate(nums):
        while queue and queue[0] <= i - k:
            queue.popleft()
        while queue and nums[queue[-1]] <= value:
            queue.pop()
        queue.append(i)
        if i >= k - 1:
            ans.append(nums[queue[0]])
    return ans

def remove_nodes(head, target):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

def merge_lists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

def cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            seeker = head
            while seeker is not slow:
                seeker, slow = seeker.next, slow.next
            return seeker
    return None

def intersection(a, b):
    p, q = a, b
    while p is not q:
        p = p.next if p else b
        q = q.next if q else a
    return p

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next
        group_next = kth.next
        prev, cur = group_next, group_prev.next
        while cur is not group_next:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        old_head = group_prev.next
        group_prev.next = kth
        group_prev = old_head

import heapq
from itertools import count

def merge_k_lists(lists):
    serial, heap = count(), []
    for head in lists:
        if head:
            heapq.heappush(heap, (head.val, next(serial), head))
    dummy = tail = ListNode()
    while heap:
        _, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            nxt = node.next
            heapq.heappush(heap, (nxt.val, next(serial), nxt))
    if tail is not dummy:
        tail.next = None
    return dummy.next

def copy_random_list(head):
    copies = {None: None}
    cur = head
    while cur:
        copies[cur] = RandomNode(cur.val)
        cur = cur.next
    cur = head
    while cur:
        copies[cur].next = copies[cur.next]
        copies[cur].random = copies[cur.random]
        cur = cur.next
    return copies[head]

from collections import deque

def inorder(root):
    ans, stack, cur = [], [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        ans.append(cur.val)
        cur = cur.right
    return ans

def level_order(root):
    if root is None:
        return []
    queue, ans = deque([root]), []
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ans.append(row)
    return ans

def valid_bst(root):
    def dfs(node, low, high):
        if node is None:
            return True
        return (low < node.val < high
                and dfs(node.left, low, node.val)
                and dfs(node.right, node.val, high))
    return dfs(root, -float('inf'), float('inf'))

def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

def max_path_sum(root):
    best = -float('inf')
    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return best

def tree_diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if node is None:
            return 0
        left, right = depth(node.left), depth(node.right)
        best = max(best, left + right)
        return max(left, right) + 1
    depth(root)
    return best

def tree_path_count(root, target):
    freq = {0: 1}
    def dfs(node, prefix):
        if node is None:
            return 0
        prefix += node.val
        ans = freq.get(prefix - target, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
        ans += dfs(node.left, prefix) + dfs(node.right, prefix)
        freq[prefix] -= 1
        if freq[prefix] == 0:
            del freq[prefix]
        return ans
    return dfs(root, 0)

def build_pre_in(preorder, inorder_values):
    positions = {x: i for i, x in enumerate(inorder_values)}
    pre_index = 0
    def build(left, right):  # 中序半开区间 [left,right)
        nonlocal pre_index
        if left >= right:
            return None
        value = preorder[pre_index]
        pre_index += 1
        mid = positions[value]
        root = TreeNode(value)
        root.left = build(left, mid)
        root.right = build(mid + 1, right)
        return root
    return build(0, len(inorder_values))

def subsets(nums):
    ans, path = [], []
    def dfs(start):
        ans.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
    dfs(0)
    return ans

def combinations(n, k):
    ans, path = [], []
    def dfs(start):
        if len(path) == k:
            ans.append(path.copy())
            return
        need = k - len(path)
        for x in range(start, n - need + 2):
            path.append(x)
            dfs(x + 1)
            path.pop()
    dfs(1)
    return ans

def permutations(nums):  # nums 元素互异
    ans, path, used = [], [], [False] * len(nums)
    def dfs():
        if len(path) == len(nums):
            ans.append(path.copy())
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False
    dfs()
    return ans

def combination_sum(candidates, target):
    a = sorted(candidates)
    ans, path = [], []
    def dfs(start, remain):
        if remain == 0:
            ans.append(path.copy())
            return
        for i in range(start, len(a)):
            if a[i] > remain:
                break
            path.append(a[i])
            dfs(i, remain - a[i])  # 同一值可再选
            path.pop()
    dfs(0, target)
    return ans

def generate_parentheses(n):
    ans = []
    def dfs(path, left, right):
        if left == right == n:
            ans.append(path)
            return
        if left < n:
            dfs(path + '(', left + 1, right)
        if right < left:
            dfs(path + ')', left, right + 1)
    dfs('', 0, 0)
    return ans

def palindrome_partitions(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j-i < 2 or pal[i+1][j-1])
    ans, path = [], []
    def dfs(start):
        if start == n:
            ans.append(path.copy())
            return
        for end in range(start, n):
            if pal[start][end]:
                path.append(s[start:end+1])
                dfs(end + 1)
                path.pop()
    dfs(0)
    return ans

def n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    path, ans = [], []
    def dfs(row):
        if row == n:
            ans.append(['.'*c + 'Q' + '.'*(n-c-1) for c in path])
            return
        for c in range(n):
            if c in cols or row-c in diag1 or row+c in diag2:
                continue
            cols.add(c); diag1.add(row-c); diag2.add(row+c)
            path.append(c)
            dfs(row + 1)
            path.pop()
            cols.remove(c); diag1.remove(row-c); diag2.remove(row+c)
    dfs(0)
    return ans

from functools import lru_cache

def fib_memo(n):
    @lru_cache(None)
    def dfs(k):
        if k < 2:
            return k
        return dfs(k-1) + dfs(k-2)
    return dfs(n)

def fib_rolling(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fib_fast(n):
    def pair(k):
        if k == 0:
            return 0, 1
        a, b = pair(k // 2)
        c = a * (2*b - a)
        d = a*a + b*b
        return (d, c+d) if k % 2 else (c, d)
    return pair(n)[0]

def island_stats(grid):
    if not grid or not grid[0]:
        return 0, 0
    m, n = len(grid), len(grid[0])
    count = largest = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] != 1:
                continue
            count += 1
            grid[r][c] = 0
            stack, area = [(r, c)], 0
            while stack:
                x, y = stack.pop()
                area += 1
                for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 0
                        stack.append((nx, ny))
            largest = max(largest, area)
    return count, largest

from collections import deque

def rotting_oranges(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r+dr, c+dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

def word_exists(board, word):
    if not word:
        return True
    if not board or not board[0]:
        return False
    m, n = len(board), len(board[0])
    marker = object()
    def dfs(r, c, i):
        if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[i]:
            return False
        if i == len(word)-1:
            return True
        old = board[r][c]
        board[r][c] = marker
        try:
            return any(dfs(r+dr, c+dc, i+1)
                       for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
        finally:
            board[r][c] = old
    return any(dfs(r, c, 0) for r in range(m) for c in range(n))

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

def max_subarray(nums):
    end = best = nums[0]
    for i in range(1, len(nums)):
        end = max(nums[i], end + nums[i])
        best = max(best, end)
    return best

def max_product(nums):
    high = low = best = nums[0]
    for i in range(1, len(nums)):
        x = nums[i]
        old_high, old_low = high, low
        high = max(x, old_high*x, old_low*x)
        low = min(x, old_high*x, old_low*x)
        best = max(best, high)
    return best

def obstacle_paths(grid):
    if not grid or not grid[0]:
        return 0
    dp = [0] * len(grid[0])
    dp[0] = 1
    for row in grid:
        for c, blocked in enumerate(row):
            if blocked:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c-1]
    return dp[-1]

def min_path_sum(grid):
    n = len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for row in grid:
        for c, value in enumerate(row):
            dp[c] = min(dp[c], dp[c-1] if c else float('inf')) + value
    return dp[-1]

def pascal_triangle(rows):
    ans = []
    for i in range(rows):
        row = [1] * (i+1)
        for j in range(1, i):
            row[j] = ans[-1][j-1] + ans[-1][j]
        ans.append(row)
    return ans

from bisect import bisect_left

def word_break(s, words):
    vocab = set(words)
    limit = max(map(len, vocab), default=0)
    dp = [False] * (len(s)+1)
    dp[0] = True
    for i in range(1, len(s)+1):
        for j in range(max(0, i-limit), i):
            if dp[j] and s[j:i] in vocab:
                dp[i] = True
                break
    return dp[-1]

def lis_length(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)  # 严格递增：首个 >= x
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)  # tails 本身未必是原序列的一个子序列

def lcs_length(a, b):
    dp = [0] * (len(b)+1)
    for x in a:
        diagonal = 0
        for j, y in enumerate(b, 1):
            old_up = dp[j]
            if x == y:
                dp[j] = diagonal + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            diagonal = old_up
    return dp[-1]

def edit_distance(a, b):
    dp = list(range(len(b)+1))
    for i, x in enumerate(a, 1):
        diagonal = dp[0]
        dp[0] = i
        for j, y in enumerate(b, 1):
            old_up = dp[j]
            dp[j] = diagonal if x == y else 1 + min(diagonal, dp[j], dp[j-1])
            diagonal = old_up
    return dp[-1]