# 数组的基本操作arr = [3, 1, 4, 1, 5, 9, 2, 6]# 随机访问 —— O(1)print(arr[0])# 3print(arr[-1])# 6# 尾部追加 —— 均摊 O(1)arr.append(8)# 指定位置插入 —— O(n)arr.insert(2, 99)# 删除元素 —— O(n)arr.remove(1)# 删除第一个值为 1 的元素# 遍历 —— O(n)for i, val in enumerate(arr):    print(f”arr[{i}] = {val}”)

s = ”Hello, 算法世界”# 切片 —— O(k)，k 为切片长度print(s[0:5])# Hello# 查找子串 —— O(n)print(s.find(”算法”))# 7# 替换 —— O(n)print(s.replace(”世界”, ”入门”))# 分割 —— O(n)print(”a,b,c”.split(”,”))# ['a', 'b', 'c']# 判断与转换print(”123”.isdigit())# Trueprint(”AbC”.lower())# 'abc'

arr = [5, 2, 8, 1, 9, 3]# 升序排序（原地）arr.sort()# 降序排序arr.sort(reverse=True)# 按自定义键排序words = [”apple”, ”banana”, ”kiwi”, ”pear”]words.sort(key=len)# 按长度排序# 稳定排序：先按长度，再按字母序words.sort(key=lambda x: (len(x), x))

def quick_sort(nums):    if len(nums) <= 1:        return nums    pivot = nums[len(nums) // 2]    left = [x for x in nums if x < pivot]    mid = [x for x in nums if x == pivot]    right = [x for x in nums if x > pivot]    return quick_sort(left) + mid + quick_sort(right)

def build_prefix_sum(nums):    pre = [0] * (len(nums) + 1)    for i in range(len(nums)):        pre[i + 1] = pre[i] + nums[i]    return predef range_sum(pre, left, right):    ”””返回 nums[left..right] 的区间和（闭区间）”””    return pre[right + 1] - pre[left]nums = [1, 2, 3, 4, 5]pre = build_prefix_sum(nums)print(range_sum(pre, 1, 3))# 2 + 3 + 4 = 9

# 经典示例：计算阶乘def factorial(n):    if n <= 1:# 终止条件        return 1    return n * factorial(n - 1)# 递归体# 斐波那契数列（带记忆化）def fib(n, memo={}):    if n in memo:        return memo[n]    if n <= 1:        return n    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)    return memo[n]

# for 循环遍历可迭代对象for i in range(5):    print(i)# while 循环 —— 适用于不确定迭代次数left, right = 0, 10while left < right:    mid = (left + right) // 2    left = mid + 1# 列表推导式 —— Pythonic 的循环写法squares = [x ** 2 for x in range(10)]

def max_sum_subarray(nums, k):    ”””固定窗口大小 k 的最大子数组和”””    window_sum = sum(nums[:k])    max_sum = window_sum    for i in range(k, len(nums)):        window_sum += nums[i] - nums[i - k]        max_sum = max(max_sum, window_sum)    return max_sumdef longest_substring_without_repeating(s):    ”””变长窗口：最长无重复字符子串”””    seen = {}    left = 0    max_len = 0    for right, ch in enumerate(s):        if ch in seen and seen[ch] >= left:            left = seen[ch] + 1        seen[ch] = right        max_len = max(max_len, right - left + 1)    return max_len

def two_sum_sorted(nums, target):    ”””对撞指针：在有序数组中找两数之和”””    left, right = 0, len(nums) - 1    while left < right:        s = nums[left] + nums[right]        if s == target:            return [left, right]        elif s < target:            left += 1        else:            right -= 1    return []def remove_duplicates(nums):    ”””快慢指针：原地去重有序数组”””    if not nums:        return 0    slow = 0    for fast in range(1, len(nums)):        if nums[fast] != nums[slow]:            slow += 1            nums[slow] = nums[fast]    return slow + 1

stack = []# 入栈 —— O(1)stack.append(1)stack.append(2)stack.append(3)# 出栈 —— O(1)print(stack.pop())# 3# 查看栈顶 —— O(1)print(stack[-1])# 2# 典型应用：括号匹配def is_valid_brackets(s):    pair = {')': '(', ']': '[', '}': '{'}    stack = []    for ch in s:        if ch in pair:            if not stack or stack.pop() != pair[ch]:                return False        else:            stack.append(ch)    return not stack

# 十进制转其他进制n = 255print(bin(n))# '0b11111111'  二进制print(oct(n))# '0o377'       八进制print(hex(n))# '0xff'        十六进制# 其他进制转十进制print(int('1010', 2))# 10print(int('1A', 16))# 26# 通用进制转换（2-36 进制）def to_base(n, base):    digits = ”0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ”    if n == 0:        return ”0”    result = []    while n > 0:        result.append(digits[n % base])        n //= base    return ''.join(reversed(result))print(to_base(255, 2))# 11111111print(to_base(255, 16))# FF

a, b = 5, 3# 5 = 0101, 3 = 0011print(a & b)# 1   (0101 & 0011 = 0001)  按位与print(a | b)# 7   (0101 | 0011 = 0111)  按位或print(a ^ b)# 6   (0101 ^ 0011 = 0110)  按位异或print(~a)# -6  按位取反print(a << 1)# 10  左移一位 = 乘以 2print(a >> 1)# 2   右移一位 = 整除 2# 常用技巧def is_odd(n):    return n & 1 == 1# 判断奇偶def is_power_of_two(n):    return n > 0 and (n & (n - 1)) == 0# 2 的幂def count_bits(n):    ”””统计二进制中 1 的个数”””    count = 0    while n:        n &= n - 1        count += 1    return count

from collections import dequeq = deque()# 入队 —— O(1)q.append(1)q.append(2)q.append(3)# 出队 —— O(1)print(q.popleft())# 1# 查看队首和队尾 —— O(1)print(q[0])# 2print(q[-1])# 3# 双端队列也支持右侧操作q.appendleft(0)# 左侧入队q.pop()# 右侧出队

# dict —— 键值对映射d = {}d[”apple”] = 1d[”banana”] = 2print(d.get(”apple”, 0))# 1print(d.get(”grape”, 0))# 0（默认值）# 遍历for key, val in d.items():    print(f”{key}: {val}”)# set —— 无序不重复集合s = {1, 2, 3}s.add(4)s.remove(2)print(3 in s)# Trueprint(s & {1, 3, 5})# {1, 3}  交集# 典型应用：两数之和def two_sum(nums, target):    seen = {}    for i, num in enumerate(nums):        diff = target - num        if diff in seen:            return [seen[diff], i]        seen[num] = i    return []

class ListNode:    def __init__(self, val=0, next_node=None):        self.val = val        self.next = next_node# 反转链表（迭代法）def reverse_list(head):    prev = None    curr = head    while curr:        nxt = curr.next        curr.next = prev        prev = curr        curr = nxt    return prev# 检测环（快慢指针）def has_cycle(head):    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow == fast:            return True    return False# 合并两个有序链表def merge_two_lists(l1, l2):    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 or l2    return dummy.next

# Python list 是顺序表的典型实现seq_list = [10, 20, 30, 40]# 自定义简单链表实现线性表接口class LinearList:    def __init__(self):        self.data = []    def get(self, index):        return self.data[index]# O(1)    def insert(self, index, val):        self.data.insert(index, val)# O(n)    def remove(self, index):        return self.data.pop(index)# O(n)    def size(self):        return len(self.data)# O(1)

def binary_search(nums, target):    left, right = 0, len(nums) - 1    while left <= right:        mid = left + (right - left) // 2        if nums[mid] == target:            return mid        elif nums[mid] < target:            left = mid + 1        else:            right = mid - 1    return -1# 查找第一个大于等于 target 的位置（lower_bound）def lower_bound(nums, target):    left, right = 0, len(nums)    while left < right:        mid = left + (right - left) // 2        if nums[mid] < target:            left = mid + 1        else:            right = mid    return left# 二分查找的泛化：在单调函数上搜索def sqrt_binary(x, eps=1e-6):    ”””用二分法求平方根”””    low, high = 0, max(1, x)    while high - low > eps:        mid = (low + high) / 2        if mid * mid < x:            low = mid        else:            high = mid    return (low + high) / 2

# 创建 3x4 矩阵matrix = [[0] * 4 for _ in range(3)]# 初始化矩阵matrix = [    [1, 2, 3],    [4, 5, 6],    [7, 8, 9]]# 遍历for i in range(len(matrix)):    for j in range(len(matrix[0])):        print(f”({i},{j})={matrix[i][j]}”, end=” ”)    print()# 矩阵转置def transpose(mat):    return [list(row) for row in zip(*mat)]# 顺时针旋转 90°def rotate_90(mat):    return [list(row)[::-1] for row in zip(*mat)]# 螺旋遍历def spiral_order(mat):    if not mat:        return []    top, bottom = 0, len(mat) - 1    left, right = 0, len(mat[0]) - 1    result = []    while top <= bottom and left <= right:        for j in range(left, right + 1):            result.append(mat[top][j])        top += 1        for i in range(top, bottom + 1):            result.append(mat[i][right])        right -= 1        if top <= bottom:            for j in range(right, left - 1, -1):                result.append(mat[bottom][j])            bottom -= 1        if left <= right:            for i in range(bottom, top - 1, -1):                result.append(mat[i][left])            left += 1    return result

import retext = ”联系电话：138-1234-5678，邮箱：user@example.com”# 匹配手机号pattern = r”1[3-9]\d-\d{4}-\d{4}”match = re.search(pattern, text)print(match.group())# 138-1234-5678# 匹配邮箱emails = re.findall(r”[\w\.-]+@[\w\.-]+\.\w+”, text)print(emails)# ['user@example.com']# 替换cleaned = re.sub(r”\d{3}-\d{4}-\d{4}”, ”***-****-****”, text)print(cleaned)# 常用元字符速查# .  匹配任意字符（除换行）# \d 数字  \w 字母数字下划线  \s 空白# *  0或多次  +  1或多次  ?  0或1次# {n} 恰好n次  {n,m} n到m次# ^  开头  $  结尾# () 分组  |  或

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right# 前序遍历（根 → 左 → 右）def preorder(root):    if not root:        return []    return [root.val] + preorder(root.left) + preorder(root.right)# 中序遍历（左 → 根 → 右）def inorder(root):    if not root:        return []    return inorder(root.left) + [root.val] + inorder(root.right)# 后序遍历（左 → 右 → 根）def postorder(root):    if not root:        return []    return postorder(root.left) + postorder(root.right) + [root.val]# 层序遍历（BFS）from collections import dequedef level_order(root):    if not root:        return []    result, q = [], deque([root])    while q:        level = []        for _ in range(len(q)):            node = q.popleft()            level.append(node.val)            if node.left:                q.append(node.left)            if node.right:                q.append(node.right)        result.append(level)    return result# 求树的最大深度def max_depth(root):    if not root:        return 0    return 1 + max(max_depth(root.left), max_depth(root.right))

def dfs_graph(adj, start):    ”””邻接表图的 DFS 递归实现”””    visited = set()    result = []    def dfs(node):        visited.add(node)        result.append(node)        for neighbor in adj.get(node, []):            if neighbor not in visited:                dfs(neighbor)    dfs(start)    return resultdef dfs_iterative(adj, start):    ”””DFS 迭代实现（显式栈）”””    visited = set()    stack = [start]    result = []    while stack:        node = stack.pop()        if node not in visited:            visited.add(node)            result.append(node)            stack.extend(adj.get(node, []))    return result# 示例：无向图graph = {    0: [1, 2],    1: [0, 3, 4],    2: [0, 5],    3: [1],    4: [1],    5: [2]}print(dfs_graph(graph, 0))# [0, 1, 3, 4, 2, 5]

from collections import dequedef bfs_graph(adj, start):    ”””邻接表图的 BFS”””    visited = set([start])    q = deque([start])    result = []    while q:        node = q.popleft()        result.append(node)        for neighbor in adj.get(node, []):            if neighbor not in visited:                visited.add(neighbor)                q.append(neighbor)    return result# 最短路径（无权图）def shortest_path(adj, start, target):    visited = set([start])    q = deque([(start, 0)])# (节点, 距离)    while q:        node, dist = q.popleft()        if node == target:            return dist        for neighbor in adj.get(node, []):            if neighbor not in visited:                visited.add(neighbor)                q.append((neighbor, dist + 1))    return -1# 示例graph = {0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1, 5], 4: [2, 5], 5: [3, 4]}print(bfs_graph(graph, 0))# [0, 1, 2, 3, 4, 5]print(shortest_path(graph, 0, 5))# 3

from collections import defaultdictimport heapqclass Graph:    def __init__(self):        self.adj = defaultdict(list)    def add_edge(self, u, v, weight=1):        self.adj[u].append((v, weight))        self.adj[v].append((u, weight))# 无向图# Dijkstra 最短路径（非负权）def dijkstra(graph, start):    dist = {start: 0}    pq = [(0, start)]    while pq:        d, u = heapq.heappop(pq)        if d > dist.get(u, float('inf')):            continue        for v, w in graph.adj[u]:            nd = d + w            if nd < dist.get(v, float('inf')):                dist[v] = nd                heapq.heappush(pq, (nd, v))    return dist# 拓扑排序（Kahn 算法，BFS）def topological_sort(graph, n):    indegree = [0] * n    for u in graph.adj:        for v, _ in graph.adj[u]:            indegree[v] += 1    q = deque([i for i in range(n) if indegree[i] == 0])    result = []    while q:        u = q.popleft()        result.append(u)        for v, _ in graph.adj[u]:            indegree[v] -= 1            if indegree[v] == 0:                q.append(v)    return result if len(result) == n else []# 空 = 有环

# 经典问题：活动选择（最大不重叠区间数）def max_activities(intervals):    intervals.sort(key=lambda x: x[1])# 按结束时间排序    count = 0    last_end = float('-inf')    for start, end in intervals:        if start >= last_end:            count += 1            last_end = end    return count# 跳跃游戏（最少跳跃次数）def jump_game(nums):    jumps = 0    cur_end = 0    farthest = 0    for i in range(len(nums) - 1):        farthest = max(farthest, i + nums[i])        if i == cur_end:            jumps += 1            cur_end = farthest    return jumps# 示例print(max_activities([(1, 3), (2, 5), (3, 6), (4, 7), (6, 8)]))# 输出: 3（选 (1,3), (3,6), (6,8)）

from itertools import permutations, combinations, productitems = [1, 2, 3]# 全排列print(list(permutations(items)))# [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)]# 选 k 个的组合print(list(combinations(items, 2)))# [(1,2), (1,3), (2,3)]# 笛卡尔积print(list(product(items, repeat=2)))# [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]# 手写回溯生成全排列def permute(nums):    result = []    def backtrack(path, used):        if len(path) == len(nums):            result.append(path[:])            return        for i in range(len(nums)):            if used[i]:                continue            used[i] = True            path.append(nums[i])            backtrack(path, used)            path.pop()            used[i] = False    backtrack([], [False] * len(nums))    return result

# 经典 DP：0-1 背包def knapsack(weights, values, capacity):    n = len(weights)    dp = [0] * (capacity + 1)    for i in range(n):        for w in range(capacity, weights[i] - 1, -1):            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])    return dp[capacity]# 最长递增子序列（LIS）def length_of_lis(nums):    dp = [1] * len(nums)    for i in range(len(nums)):        for j in range(i):            if nums[j] < nums[i]:                dp[i] = max(dp[i], dp[j] + 1)    return max(dp)# 编辑距离（Levenshtein Distance）def edit_distance(word1, word2):    m, n = len(word1), len(word2)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(m + 1):        dp[i][0] = i    for j in range(n + 1):        dp[0][j] = j    for i in range(1, m + 1):        for j in range(1, n + 1):            if word1[i-1] == word2[j-1]:                dp[i][j] = dp[i-1][j-1]            else:                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1],                                   dp[i-1][j-1])    return dp[m][n]# 示例print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))# 10print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))# 4print(edit_distance(”horse”, ”ros”))# 3

# N 皇后问题def solve_n_queens(n):    result = []    board = [['.'] * n for _ in range(n)]    cols = set()    diag1 = set()# 主对角线  r - c    diag2 = set()# 副对角线  r + c    def backtrack(row):        if row == n:            result.append([''.join(r) for r in board])            return        for col in range(n):            if col in cols or (row - col) in diag1 \               or (row + col) in diag2:                continue            board[row][col] = 'Q'            cols.add(col)            diag1.add(row - col)            diag2.add(row + col)            backtrack(row + 1)            board[row][col] = '.'            cols.remove(col)            diag1.remove(row - col)            diag2.remove(row + col)    backtrack(0)    return result# 子集生成def subsets(nums):    result = []    def backtrack(start, path):        result.append(path[:])        for i in range(start, len(nums)):            path.append(nums[i])            backtrack(i + 1, path)            path.pop()    backtrack(0, [])    return result

# 经典应用：字符串转整数（atoi）def my_atoi(s):    START, SIGN, NUMBER, END = 0, 1, 2, 3    state = START    sign = 1    result = 0    INT_MAX = 2**31 - 1    INT_MIN = -2**31    for ch in s:        if state == START:            if ch == ' ':                continue            elif ch in '+-':                sign = 1 if ch == '+' else -1                state = SIGN            elif ch.isdigit():                result = int(ch)                state = NUMBER            else:                break        elif state == SIGN:            if ch.isdigit():                result = int(ch)                state = NUMBER            else:                break        elif state == NUMBER:            if ch.isdigit():                digit = int(ch)                if result > (INT_MAX - digit) // 10:                    return INT_MAX if sign == 1 else INT_MIN                result = result * 10 + digit            else:                break    return sign * result# 买卖股票最佳时机（含冷冻期）—— DP + 状态机def max_profit_with_cooldown(prices):    if not prices:        return 0    hold = float('-inf')# 持有    sold = 0# 刚卖出（冷冻期）    rest = 0# 不持有（非冷冻期）    for p in prices:        prev_sold = sold        hold = max(hold, rest - p)        sold = hold + p        rest = max(rest, prev_sold)    return max(sold, rest)

class UnionFind:    def __init__(self, n):        self.parent = list(range(n))        self.rank = [0] * n    def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])# 路径压缩        return self.parent[x]    def union(self, x, y):        px, py = self.find(x), self.find(y)        if px == py:            return False        if self.rank[px] < self.rank[py]:            self.parent[px] = py        elif self.rank[px] > self.rank[py]:            self.parent[py] = px        else:            self.parent[py] = px            self.rank[px] += 1        return True    def connected(self, x, y):        return self.find(x) == self.find(y)# 典型应用：判断无向图是否有环def has_cycle(n, edges):    uf = UnionFind(n)    for u, v in edges:        if not uf.union(u, v):            return True    return False# 岛屿数量def num_islands(grid):    if not grid:        return 0    m, n = len(grid), len(grid[0])    uf = UnionFind(m * n)    count = sum(grid[i][j] == '1' for i in range(m) for j in range(n))    uf.count = count# 实际编码时可用一个 size 计数器来跟踪连通分量数    return count# 简化示意

# 归并排序def merge_sort(nums):    if len(nums) <= 1:        return nums    mid = len(nums) // 2    left = merge_sort(nums[:mid])    right = merge_sort(nums[mid:])    return merge(left, right)def merge(left, right):    result = []    i = j = 0    while i < len(left) and j < len(right):        if left[i] < right[j]:            result.append(left[i])            i += 1        else:            result.append(right[j])            j += 1    result.extend(left[i:])    result.extend(right[j:])    return result# 求数组中的逆序对数量def count_inversions(nums):    def merge_count(arr, temp, left, mid, right):        i, j, k = left, mid + 1, left        inv_count = 0        while i <= mid and j <= right:            if arr[i] <= arr[j]:                temp[k] = arr[i]                i += 1            else:                temp[k] = arr[j]                inv_count += (mid - i + 1)                j += 1            k += 1        while i <= mid:            temp[k] = arr[i]            i += 1            k += 1        while j <= right:            temp[k] = arr[j]            j += 1            k += 1        for i in range(left, right + 1):            arr[i] = temp[i]        return inv_count    def sort_count(arr, temp, left, right):        inv_count = 0        if left < right:            mid = (left + right) // 2            inv_count += sort_count(arr, temp, left, mid)            inv_count += sort_count(arr, temp, mid + 1, right)            inv_count += merge_count(arr, temp, left, mid, right)        return inv_count    return sort_count(nums[:], [0]*len(nums), 0, len(nums)-1)

# 枚举所有子集def enumerate_subsets(nums):    n = len(nums)    result = []    for mask in range(1 << n):# 0 到 2^n - 1        subset = []        for i in range(n):            if mask & (1 << i):                subset.append(nums[i])        result.append(subset)    return result# 枚举 + 剪枝：三数之和为 0def three_sum(nums):    nums.sort()    result = []    n = len(nums)    for i in range(n - 2):        if i > 0 and nums[i] == nums[i - 1]:            continue# 剪枝：去重        if nums[i] + nums[i+1] + nums[i+2] > 0:            break# 剪枝：最小值之和 > 0        if nums[i] + nums[n-2] + nums[n-1] < 0:            continue# 剪枝：最大值之和 < 0        left, right = i + 1, n - 1        while left < right:            s = nums[i] + nums[left] + nums[right]            if s == 0:                result.append([nums[i], nums[left], nums[right]])                while left < right and nums[left] == nums[left+1]:                    left += 1                while left < right and nums[right] == nums[right-1]:                    right -= 1                left += 1                right -= 1            elif s < 0:                left += 1            else:                right -= 1    return result

from collections import Counter# 频率统计data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]counter = Counter(data)print(counter.most_common(2))# [(4, 4), (3, 3)]# 多数元素（Boyer-Moore 投票算法）def majority_element(nums):    count = 0    candidate = None    for num in nums:        if count == 0:            candidate = num        count += 1 if num == candidate else -1    return candidate# 统计优美子数组（前缀和 + 计数）def number_of_subarrays(nums, k):    ”””统计恰好包含 k 个奇数的子数组数量”””    count = {0: 1}    odd_count = 0    result = 0    for num in nums:        if num % 2 == 1:            odd_count += 1        result += count.get(odd_count - k, 0)        count[odd_count] = count.get(odd_count, 0) + 1    return result# 中位数def median(nums):    nums.sort()    n = len(nums)    if n % 2 == 1:        return nums[n // 2]    return (nums[n // 2 - 1] + nums[n // 2]) / 2