二分答案模板——求最大值 vs 求最小值
二分答案模板 —— 求最大值 vs 求最小值 核心思想：在答案的可能范围 [L, R] 内，通过二分猜测 + check 函数验证，快速找到最优解。 区别于标准二分在数据里查目标，二分答案是在答案里猜最优。 一、两种模板速览模板 A：求最大值（最大的可行值）while (left < right) { int mid = (left + right + 1) / 2; if (check(mid)) { left = mid; } else { right = mid - 1; }}return left; 使用场景：求最大跳跃距离、最大载重、最大速度…… 模板 B：求最小值（最小的可行值）while (left < right) { int mid = (left + right) / 2; if (check(mid)) { right = mid; } else { ...
算法笔记：矩阵分层旋转——从「层」到「四指针」的思维转换
算法笔记：矩阵分层旋转问题 —— 从「层」到「四指针」的思维转换 日期: 2026-05-09难度: Medium标签: 矩阵、模拟、循环旋转 题目描述给定一个 m × n 的二维网格 grid 和一个整数 k。你需要将 grid 按逆时针方向循环旋转每一层，旋转 k 次。 所谓「一层」就是从外到内的一圈元素。旋转时，各层独立旋转。 第一次思路（卡住了）刚开始我的思路是这样的： 遍历层数为 level = min(m, n) / 2最开始高宽为 m 和 n，每缩一层长宽减 2当处在某一层的高宽为 h 和 w 时，一圈的元素个数为 2 * (w + h - 2) 想法是对的，但问题在于无法用一个「层序号」去直接映射到二维数组的下标。比如我知道我在第 3 层，那这一圈的左上角坐标是多少？不知道。代码写着写着就变成了各种 +1 -1 的边界调整，非常容易出 bug。 最终方案：四个方向变量这个问题的核心痛点在于如何方便地遍历和修改某一圈的元素。与其算「第几层」，不如直接维护四个指针： top — 当前层的上边界行号bottom — 当前层的下边界行号left —...
基于Dijkstra算法引生出来的一道算法题
基于Dijkstra算法引生出来的一道算法题一、Dijkstra算法基本介绍 背景 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄杰斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。 用途 该算法可以算出从一个顶点到其余各顶点的最短路径，解决的是有权图中最短路径问题。 复杂度 O((V + E) * log V） 核心思想 迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 在讲解算法步骤之前，这里先说明一下等下要用到的东西： 1.dist[]：用来记录从源点 V0 到其他各顶点当前的最短路径长度，它的初态为：若从 V0 到 Vi 有直接路径（即 V0 和 Vi 邻接），则 dist[ i ] 为这两个顶点边上的权值；否则置 dist[ i ] 为 ∞。 2.path[ ]：path[ i ] 表示从源点到顶点 i 之间的最短路径的前驱结点。在算法结束时，可以根据其值追溯到源点 V0 到 Vi...
算法日记：平衡子数组问题(LeetCode525)
算法日记：从暴力到 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++) { ...
由一道题目所引发的对于二分查找的思考
由一道题目所引发的对于二分查找的思考一、题目描述 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对 的数目。 如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ： 0 <= i < j < n，且 lower <= nums[i] + nums[j] <= upper 示例 1： 输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6输出：6解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。 示例 2： 输入：nums = [1,7,9,2,5], lower = 11, upper = 11输出：1解释：只有单个公平数对：(2,3) 。 提示： 1 <= nums.length <= 10^5 nums.length == n -10^9 <= nums[i] <= 10^9 -10^9 <= lower <= upper...
算法笔记：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：左 ↔...
LeetCode2615.等值距离和【中等】
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 =...
LeetCode1855.下标对中的最大距离【中等】
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]...
LeetCode1807.矩阵的最大非负积【中等】
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()...
LeetCode2906.构造乘积矩阵【中等】
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...