递归算法
递归算法 1. 基本概念 核心定义：递归是一种通过函数调用自身来解决问题的算法策略。它将一个复杂的大问题转化为一个或多个与原问题结构相同、但规模更小的子问题来求解。 核心思想：“大事化小，小事化了”。 如果问题很大，就把它拆成小问题（递推）。 如果问题很小（到了边界），就直接解决（回归）。 两大要素： 基准情况：递归的“出口”，即最小的、可以直接求解的问题（防止死循环）。 递归步骤：将大问题拆解，并调用自身去解决子问题。 2. 费曼理解 用最简单的语言解释给“小白”听： 想象你在电影院里，想知道自己是第几排，但太黑了看不清。 递归（问人）：你问前一排的人：“你是第几排？” 前一排的人也不知道，他只好问他前一排的人。 这个问题一直传到了第一排的人。 基准情况（出口）：第一排的人说：“我是第 1 排。” 回归（传话）： 第二排的人听到后，说：“我是第 1+1=2 排。” 第三排的人听到后，说：“我是第 2+1=3 排。” 最后传回给你，你知道了自己是第 N 排。 3. 算法核心步骤 递归算法的执行过程可以严格拆解为以下 4 个标准步骤。这是...
枚举算法
1. 基本概念 核心定义 枚举算法是一种通过逐一尝试所有可能情况来解决问题的算法策略。它不依赖复杂的逻辑推理，而是依靠计算机的高速运算能力，将问题的所有解或可能的解一一列举出来，然后根据约束条件筛选出符合条件的解。 核心思想 “宁可错杀一千，不可放过一个”。通过循环遍历所有候选解，逐一验证。 适用场景 问题规模较小，解空间有限 无法找到更高效的优化算法（如某些NP难问题） 作为验证其他高效算法正确性的"基准测试（Ground Truth）" 2. 算法核心步骤 枚举算法的执行过程可以严格拆解为以下4个标准步骤： 步骤序号 步骤名称 核心操作描述 关键问题 Step 1 确定解空间 明确问题的"搜索范围"。即确定哪些数据是候选解，以及它们的排列方式（如数组、集合、排列组合）。 “我要在哪些数据里找？” Step 2 设计循环结构 根据解空间的维度，构建嵌套循环（For/While）。如果是多维解（如矩阵），通常需要多层循环嵌套。 “我该怎么遍历所有情况？” Step 3 验证约束条件 在循环体内，编写If语...
二叉搜索树
二叉搜索树 基本概念 二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它满足：对于任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。左右子树也分别为二叉搜索树。中序遍历 BST 可以得到一个递增的有序序列。 数据结构的三要素 逻辑结构 树形结构，但节点之间具有“左小右大”的约束关系，本质上是一种动态有序表。 存储结构 链式存储：每个节点包含数据域、左孩子指针、右孩子指针。也可使用数组顺序存储（需按完全二叉树编号，但会浪费空间）。 数据的运算 查找（search）、插入（insert）、删除（delete）、求最大值/最小值、求前驱/后继、范围查询（range query）等。 费曼理解 想象你有一本按字母顺序排列的英语词典。你打开中间一页，看到单词 “M”。如果要查 “Apple”，你会往左翻（因为 A < M）；如果要查 “Zoo”，你会往右翻（Z > M）。每次翻页后，你只关注剩下的一半区域，就像二分查找。二叉搜索树就是这种思想在树结构上的体现：每个节点就像一个“分...
二叉树的还原
二叉树的还原 基本概念 二叉树的还原是指根据二叉树的两种遍历序列（如前序+中序、后序+中序）唯一确定一棵二叉树的过程。由于前序（或后序）可以确定根节点，中序可以划分左、右子树，因此通过递归分治即可重建整棵树。若缺少中序序列，则无法唯一还原。 数据结构的三要素 逻辑结构 树形结构，每个节点最多有两个子树（左/右），节点之间存在父子关系，子树不相交。 存储结构 链式存储：每个节点包含数据域、左孩子指针、右孩子指针，通过指针连接成树。 顺序存储（数组）：按完全二叉树编号存储，但还原算法通常采用链式结构。 数据的运算 根据遍历序列构建二叉树（重建）。 树的遍历（前序、中序、后序、层序）。 求树高、节点数、判断是否相同等。 费曼理解 想象有一棵家族树，前序相当于先报出“爷爷”，然后报出爷爷的左支全部，再报出右支全部；中序相当于先报出左支全部，然后报出“爷爷”，最后报出右支全部。现在你拿到两份名单（前序和中序），前序的第一个名字一定是整棵树的根（爷爷），再到中序里找到爷爷的名字，左边那一堆名字就是左子树成员，右边就是右子树成员。对左右子树重复这个“找根、分左右”...
深度优先搜索算法
深度优先搜索算法 (DFS) 深度优先搜索 (Depth-First Search) 是一种用于遍历或搜索树或图数据结构的算法。该算法从起始顶点出发，沿着一条路径尽可能深地探索，直到无法继续（遇到死胡同或已访问顶点），然后回溯到上一个分叉点，继续探索其他未访问的分支。DFS 天然适合使用递归实现，也可借助栈进行迭代模拟。 算法步骤（递归版） 标记与处理：访问起始顶点 v，将其标记为“已访问”，并进行所需处理（如记录结果）。 递归深入：依次检查 v 的每一个邻接顶点 w。 若 w 未被访问，则以 w 为新起点，递归执行步骤 1、2。 自然回溯：当 v 的所有邻接点均被访问过，当前递归调用结束，自动返回上一层调用，继续探索上一层未完成的邻接点。 终止条件：当所有从起始顶点可达的顶点均被访问后，算法结束。 123456789101112131415161718def DFS(self, start): visited = set() result = [] def dfs(v): # 1. 标记当前节点为已访问并记录 ...
任意子数组和的绝对值的最大值-LeetCode
这是一份基于你提供的代码生成的详细题解文档。 1749. 任意子数组和的绝对值的最大值 🎯 问题描述 描述： 给你一个整数数组 nums。 子数组 nums[l...r] 的和定义为 nums[l]+nums[l+1]+...+nums[r]nums[l] + nums[l+1] + ... + nums[r]nums[l]+nums[l+1]+...+nums[r]。 你需要找出所有可能的子数组和中，绝对值最大的那一个。 即求 max(∣Sum(l,r)∣)\max(|Sum(l, r)|)max(∣Sum(l,r)∣)，其中 0≤l≤r<n0 \le l \le r < n0≤l≤r<n。 说明： 这是一个前缀和结合数学推导的问题。 核心策略： 任意子数组的和都可以表示为两个前缀和之差：Sum(l,r)=pre[r+1]−pre[l]Sum(l, r) = pre[r+1] - pre[l]Sum(l,r)=pre[r+1]−pre[l]。 我们要最大化 ∣pre[r+1]−pre[l]∣|pre[r+1] - pre[l]|∣pre[r+...
区域和检索-数组不可变-LeetCode
303. 区域和检索 - 数组不可变 🎯 问题描述 描述： 给定一个整数数组 nums，处理以下类型的多个查询： 计算索引 left 和 right（包含 left 和 right）之间的 nums 元素的和。 实现 NumArray 类： NumArray(int[] nums)：使用数组 nums 初始化对象。 int sumRange(int left, int right)：返回数组 nums 中索引 left 和 right 之间（包含）的元素和。 说明： 这是一个前缀和的基础应用题。 核心策略： 利用数学性质：区间和 [left,right][left, right][left,right] 等于前缀和 [0,right][0, right][0,right] 减去前缀和 [0,left−1][0, left-1][0,left−1]。 公式：Sum(left,right)=∑i=0rightnums[i]−∑i=0left−1nums[i]Sum(left, right) = \sum_{i=0}^{right} nums[i] - \sum_{...
变长子数组求和-LeetCode
3427. 变长子数组求和 🎯 问题描述 描述： 给你一个整数数组 nums。 对于数组中的每个元素 nums[i]，我们需要计算一个特定子数组的和。 该子数组以 i 结尾，其起始位置由 nums[i] 的值决定。 具体来说，对于下标 i，子数组的起始下标为 start = max(0, i - nums[i])。 你需要返回所有这些子数组和的总和。 说明： 这是一个前缀和的应用题。 核心策略： 题目要求计算多个不同长度、不同起点的子数组和。 如果直接对每个位置都遍历求和，时间复杂度会达到 O(N2)O(N^2)O(N2)。 利用前缀和数组，我们可以在 O(1)O(1)O(1) 的时间内计算任意区间的和，从而将总复杂度降为 O(N)O(N)O(N)。 逻辑定义： 对于每个 i，计算区间 [max(0, i - nums[i]), i] 的元素和。 最后将所有计算出的和累加。 示例： 示例 1： 1234567输入：nums = [2, 1, 3]输出：7解释：- i=0: nums[0]=2. start = max(0, 0-2) = 0....
子数组异或查询-LeetCode
1310. 子数组异或查询 🎯 问题描述 描述： 给你一个正整数数组 arr（注意题目通常指非负整数），以及一个查询数组 queries，其中 queries[i] = [li, ri]。 对于每个查询 i，你必须计算 arr[li] ^ arr[li+1] ^ ... ^ arr[ri] 的结果（即从 li 到 ri 的所有元素的异或值）。 返回一个包含所有查询结果的数组。 说明： 这是一个位运算结合前缀和思想的问题。 核心策略： 异或运算满足结合律和交换律。 异或运算有一个极其重要的性质：自反性，即 a⊕a=0a \oplus a = 0a⊕a=0。 利用这一性质，我们可以通过前缀异或数组来快速计算任意区间的异或值，类似于前缀和中的区间减法。 示例： 示例 1： 123456789输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]输出：[2,7,14,8]解释：- arr = [1,3,4,8]- 前缀异或 pre = [0, 1, 1^3=2, 2^4=6, 6^8=14] ->...
对角线上不同值的数量差-LeetCode
2711. 对角线上不同值的数量差 🎯 问题描述 描述： 给你一个下标从 0 开始的 m x n 二维整数数组 grid。 你需要返回一个同样大小的矩阵 answer，其中 answer[i][j] 的值为： ∣topLeft[i][j]−bottomRight[i][j]∣| \text{topLeft}[i][j] - \text{bottomRight}[i][j] | ∣topLeft[i][j]−bottomRight[i][j]∣ 其中： topLeft[i][j] 表示单元格 (i, j) 左上角对角线（即行下标和列下标都小于 i 和 j 的方向）上不同值的数量。 bottomRight[i][j] 表示单元格 (i, j) 右下角对角线（即行下标和列下标都大于 i 和 j 的方向）上不同值的数量。 如果对角线上没有元素，则数量为 0。 说明： 这是一个矩阵对角线遍历问题。 核心策略： 同一条主对角线（左上到右下）上的元素，其坐标差 i - j 是恒定的。 我们可以根据 i - j 的值将矩阵元素分组到不同的对角线上。 对于每一条对角线，我们需...
