【一起来学AI大模型】算法核心：数组/哈希表/树/排序/动态规划（LeetCode精练）

以下是五大核心算法的重点解析和LeetCode经典题解，包含最优解法和模板代码：

一、数组操作（双指针/滑动窗口）

核心思想：通过索引指针高效遍历与操作数组

1. 移动零（No.283）

def moveZeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

2. 盛最多水的容器（No.11）

def maxArea(height):
    left, right = 0, len(height)-1
    max_area = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

3. 最小覆盖子串（No.76）滑动窗口模板

def minWindow(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    
    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        
        if missing == 0:  # 窗口满足条件
            # 收缩左边界
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            # 更新结果
            if not end or right-left <= end-start:
                start, end = left, right
            # 移动左边界
            need[s[left]] += 1
            missing += 1
            left += 1
            
    return s[start:end]

二、哈希表应用（快速查找）

核心思想：空间换时间，实现O(1)查找

1. 两数之和（No.1）

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

2. 字母异位词分组（No.49）

def groupAnagrams(strs):
    from collections import defaultdict
    d = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        d[key].append(s)
    return list(d.values())

3. 最长连续序列（No.128）

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    
    for num in num_set:
        # 确保从序列起点开始
        if num-1 not in num_set:
            curr = num
            curr_len = 1
            
            while curr+1 in num_set:
                curr += 1
                curr_len += 1
                
            max_len = max(max_len, curr_len)
            
    return max_len

三、树形结构（递归/迭代）

核心思想：分治思想处理子树，栈/队列辅助迭代

1. 二叉树的最大深度（No.104）

# 递归
def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# 迭代（BFS）
from collections import deque
def maxDepth(root):
    if not root: return 0
    queue = deque([root])
    depth = 0
    
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
    
    return depth

2. 验证二叉搜索树（No.98）

def isValidBST(root):
    def valid(node, low=-float('inf'), high=float('inf')):
        if not node: return True
        if node.val <= low or node.val >= high:
            return False
        return (valid(node.left, low, node.val) and 
                valid(node.right, node.val, high))
    return valid(root)

3. 二叉树的最近公共祖先（No.236）

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right: return root
    return left if left else right

四、排序算法（归并/快排）

核心思想：分治策略实现高效排序

1. 快速排序模板

def quick_sort(arr, l, r):
    if l >= r: return
    # 分区操作
    pivot = partition(arr, l, r)
    quick_sort(arr, l, pivot-1)
    quick_sort(arr, pivot+1, r)

def partition(arr, l, r):
    import random
    # 随机选择基准避免最坏情况
    rand_idx = random.randint(l, r)
    arr[rand_idx], arr[r] = arr[r], arr[rand_idx]
    
    pivot_val = arr[r]
    i = l
    for j in range(l, r):
        if arr[j] < pivot_val:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[r] = arr[r], arr[i]
    return i

2. 合并区间（No.56）

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

3. 数组中的第K个最大元素（No.215）

def findKthLargest(nums, k):
    import heapq
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

五、动态规划（状态转移）

核心思想：定义状态与状态转移方程，避免重复计算

1. 爬楼梯（No.70）基础模板

def climbStairs(n):
    if n <= 2: return n
    dp = [0]*(n+1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

2. 最长递增子序列（No.300）

# 标准DP解法 O(n²)
def lengthOfLIS(nums):
    dp = [1]*len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

# 贪心+二分 O(nlogn)
def lengthOfLIS(nums):
    tails = []  # 存储最小尾部元素
    for num in nums:
        # 二分查找插入位置
        l, r = 0, len(tails)
        while l < r:
            mid = (l+r)//2
            if tails[mid] < num:
                l = mid+1
            else:
                r = mid
        if l == len(tails):
            tails.append(num)
        else:
            tails[l] = num
    return len(tails)

3. 编辑距离（No.72）经典二维DP

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    
    # 初始化边界
    for i in range(1, m+1): dp[i][0] = i
    for j in range(1, 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]

六、综合训练题库（按难度排序）

高效训练建议：

1. 每日专项训练：每天专注1个算法类型（如周一数组/周二哈希表）

2. 三遍刷题法：

• 第一遍：独立解题（30分钟）

• 第二遍：学习最优解并复现

• 第三遍：隔周重做+总结模板

1. 重点突破：

• 双指针（数组/字符串）

• 回溯法（树形问题）

• 状态机（动态规划）

• 堆应用（排序/TOP K问题）

核心技巧：

• 数组：左右指针/快慢指针/前缀和

• 哈希表：空间换时间/计数器

• 树：递归三要素（终止条件/本级任务/返回值）

• 排序：归并分治/快速选择

• DP：状态定义 → 转移方程 → 初始化 → 遍历顺序