前缀和与哈希 —— 平衡子数组
算法日记：从暴力到 O(n) 的线性飞跃 —— 平衡子数组问题(leetcode525)1. 直觉：暴力 (O(n^2))最开始拿到这道题，最直观的反应是：枚举所有的子数组。 做法：双层 for 循环，外层固定起点 i，内层枚举终点 j。 判断：统计 [i, j] 区间内 0 和 1 的个数是否相等。 瓶颈：随着 n 的增加，计算量呈平方级增长。当 n = 10^5 时，明显超出题目规定范围。 2. 数学建模：前缀和的引入 (O(n^2))为了优化掉内层的重复计数，我引入了前缀和。 转换思维：把 0 看作 -1，把 1 看作 1。 核心结论：如果一个子数组 $[i, j]$ 满足 0 和 1 的个数相等，那么它的区间和必为 0。 前缀和公式：$$\text{preSum}[j + 1] - \text{preSum}[i] = 0$$ 代码实现： // 第一版逻辑：前缀和 + 暴力查找for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { ...
DFS变通 —— 路径检查到环检测
算法笔记：DFS 模板的变通——从路径检查到环检测 日期: 2026-04-27主题: DFS、图论、模板变通难度: Medium标签: DFS、BFS、有向图、无向图找环、表驱动 一、写在前面最近连续做了两道 DFS 题，一道是检查网格中的有效路径（1391），一道是探测相同值形成的环（1559）。两道题都用到了 DFS，但和之前做过的”岛屿问题”、”填海造陆”那种标准遍历模板不太一样——不是拿着 void dfs(x, y) 直接搜就行，而是要根据题意在基础模板上做不少变通。 做完之后我发现，自己正在经历一个从”背模板”到”理解原理然后变通”的阶段。这种感受很难得，趁热记录下来。 二、LeetCode 1391. 检查网格中是否存在有效路径 题目链接: https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/难度: Medium标签: DFS、表驱动、BFS 题目描述给定一个 m × n 的网格，每个格子代表一条街道，有 6 种类型： 1：左 ↔ 右 2：上 ↔ 下 3：左 ↔...
前缀和与哈希 —— 等值距离和
LeetCode 2615. 等值距离和 题目链接: https://leetcode.cn/problems/sum-of-distances/日期: 2026-04-23难度: Medium标签: 哈希表、前缀和、数学优化 一、题目描述给定一个整数数组 nums，构造数组 arr，使得 arr[i] 等于所有满足 nums[j] == nums[i] 且 j != i 的 |i - j| 之和。如果不存在这样的 j，则 arr[i] = 0。 示例 1： 输入：nums = [1,3,1,1,2]输出：[5,0,3,4,0]解释：i = 0：nums[0] == nums[2] == nums[3]，arr[0] = |0-2| + |0-3| = 5i = 1：没有其他位置的值为 3，arr[1] = 0i = 2：nums[2] == nums[0] == nums[3]，arr[2] = |2-0| + |2-3| = 3i = 3：nums[3] == nums[0] == nums[2]，arr[3] = |3-0| + |3-2| = 4i =...
双指针与二分答案 —— 最大距离问题
LeetCode 1855. 下标对中的最大距离 题目链接: https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/日期: 2026-04-19难度: Medium标签: 二分查找、双指针、单调性利用 一、题目描述给定两个非递增整数数组 nums1 和 nums2，下标从 0 开始。 定义一个有效下标对 (i, j) 需要满足： 0 <= i < nums1.length 0 <= j < nums2.length i <= j nums1[i] <= nums2[j] 该下标对的距离定义为 j - i。 求所有有效下标对中的最大距离。如果不存在有效下标对，返回 0。 二、踩坑回顾第一次尝试：暴力枚举for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { if (i <= j && nums1[i]...
前后缀积 —— 构造乘积矩阵
LeetCode 2906. 构造乘积矩阵 题目链接: https://leetcode.cn/problems/construct-product-matrix/日期: 2026-03-23难度: Medium标签: 前缀和、模运算、取模技巧 一、题目描述给定一个 n × m 的二维矩阵 grid，定义 p[i][j] 为：矩阵中除 grid[i][j] 外所有元素的乘积，对 12345 取模。 要求返回乘积矩阵 p。 提示： 2 ≤ n × m ≤ 10^5 1 ≤ grid[i][j] ≤ 10^9 不能使用除法 二、踩坑回顾第一次尝试：除法不可行看到这道题的第一反应是：先算出所有元素的乘积，然后逐个除以当前元素。 long long total = 1;for (int r = 0; r < n; r++) for (int c = 0; c < m; c++) total *= grid[r][c];p[r][c] = (total / grid[r][c]) % MOD; 问题一：total 会溢出。10^9 的 10^5...
图上DP —— 矩阵最大非负积
LeetCode 1807. 矩阵的最大非负积 题目链接: https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/日期: 2026-03-23难度: Medium标签: 动态规划、状态机思维 一、题目描述给定一个 m × n 的矩阵 grid，从左上角 (0, 0) 出发，只能向右或向下移动，最终到达右下角 (m-1, n-1)。 沿路径访问的单元格中所有整数的乘积即为该路径的积。 求所有路径中，最大非负积是多少？如果最大积为负数，返回 -1。 注意：最终答案要对 10^9 + 7 取模。 二、踩坑回顾第一次尝试：DFS 暴力枚举看到 m, n ≤ 15 不大，直觉上直接遍历所有路径应该可行。于是写了这样的 DFS： void dfs(vector<vector<int>>& grid, int r, int c, long long num) { num *= grid[r][c]; if (r + c == grid.size()...
回溯到DP —— 记忆化与状态压缩
算法笔记：从回溯到 DP 的优化之路 日期: 2026-03-10主题: 记忆化搜索与动态规划难度: Medium → Hard标签: DP、记忆化搜索、状态转移、容斥原理 一、核心思想 记忆化的本质：把重复的子问题答案存起来，下次直接用。 关键问题：什么构成了一个唯一的状态？ 优化路径┌─────────────────────────────────────────────────┐│ 回溯 (暴力枚举) │ 复杂度：O(2^n) 或 O(8^n) ❌ │ 问题：大量重复计算 └─────────────────────────────────────────────────┘ ↓┌─────────────────────────────────────────────────┐│ 记忆化搜索 (自顶向下) ...
滑动窗口 —— 交替字符串最小翻转
LeetCode 2864. 使二进制字符串交替的最小翻转次数 题目链接: https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/日期: 2026-03-07难度: Medium标签: 滑动窗口、字符串、贪心 题目描述给定一个二进制字符串 s，你可以执行两种操作： 将首元素移到末尾（循环移位） 任选一个元素反转（0→1 或 1→0） 求将 s 转换成交替字符串（如 “010101…” 或 “101010…”）所需的最少操作 2 的次数。 解题思路关键洞察 操作 1 的本质：不需要真正去截取首元素放到末尾，而是通过 拼接 s + s 来模拟循环移位。这样问题转化为：在长度为 2n 的字符串中，找一个长度为 n 的窗口，使其最接近目标交替串。 滑动窗口优化：如果暴力遍历每个窗口的所有元素，时间复杂度为 O(n²)，不可接受。关键观察是：窗口每次只滑动一格，只有左右边界元素发生变化，中间元素不变。因此可以用一个全局变量 diff...
《分苹果问题：从暴力模拟到二分优化的一步步思考》
一、题目背景 有 n 个孩子和 m 个苹果，每个孩子至少分一个，且相邻两个孩子的苹果数差值不能超过 1，求在满足条件的前提下，小明（第 k 个孩子）最多可以分到多少苹果？ 二、思路分析 相邻两个孩子的苹果数量不能大于一而且小明需要尽可能的多分，所以最后肯定是一个以小明为峰顶的一个“山峰”形状。 所以问题的关键就是我们假设小明分到了 x 个苹果，然后根据小明的位置分别计算出左右两边需要的苹果数量，并判断数量是否足够，如果足够的话就将加 x 加一然后继续判断，直到 m 个苹果不够分为止。 三、关键实现逻辑 关键在于苹果数量的计算，现在我们假设分给了小明 x 个苹果，然后小明的位置在 k，他左边有 k-1 个人，右边有 n-k 个人，现在以从左边开始举例子（应为右边的计算方式也是一样）。 这里要分两种情况讨论一下： 1、x - 1 >= k - 1 这种情况下我们可以简单的计算苹果的数量，就是一个等差数列，将首项加上未项乘以项数除以 2 即可得到结果。 2、x - 1 < k -...
LeetCode416.分割等和子集【中等】
相关标签： 数组、动态规划 题目简介： 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例： 示例 1： 输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2： 输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。 提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100 解题思路： 题目要求我们分割等和子集，那首先想到的就是排除和为奇数的情况，当和为偶数时才有讨论的必要。我们现在的目标就变成了判断能否从数组中找出一些元素凑成总和的一半。 诶，这个描述是不是有一点耳熟，我换一个说法你就明白了，给你一个背包，让你判断能否将背包装满。所以这道题本质上就是背包问题，而且是 01 背包问题（不允许重复）。 唯一需要注意的一点就是这里的 dp 数组需要定义成 boolean...