相邻差分组 —— 排序数组连通分量
相邻差分组 —— 排序数组连通分量 日期: 2026-07-09难度: Medium标签: 排序、连通性、分组题目链接: 3532. 针对图的路径存在性查询 I 题目描述有 n 个节点，每个节点 i 有权值 nums[i]（数组已排序）。若 |nums[i] - nums[j]| <= maxDiff，则 i 和 j 之间有无向边。此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。 第一次思路暴力建图 O(n²) → 超时 第一反应是两层循环检查每一对节点，满足条件就加边，然后每次查询 BFS 判连通。建图就是 O(n²)，n 最大 1e5，不出意外的超时。 vector<vector<int>> edge(n);for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if...
多源BFS与二分答案 —— 最大安全系数路径
多源BFS + 二分答案 —— 最大安全系数路径 日期: 2026-07-1难度: Medium标签: 多源BFS、二分答案、连通性题目链接: 2812. 找出最安全路径 题目简述给定一个 n×n 的 01 矩阵，1 表示小偷，0 表示空。路径的安全系数定义为路径上所有点到任一小偷的最小曼哈顿距离。求从 (0,0) 到 (n-1,n-1) 的所有路径中，安全系数的最大值。 第一次思路读完题首先想到两个方向： 需要算每个格子的安全距离 然后要找一个最大安全系数。 但是有三个地方卡住了： 多源BFS —— 多个小偷怎么一次算完？第一反应是对每个小偷单独 BFS，然后再对每个格子取 min。这显然太慢——小偷数量可能很多，每次 BFS 都是 O(n²)，总复杂度不行。正确做法应该是是多源 BFS：把所有小偷一次性全部入队，BFS 同时从所有源点向外扩散，第一个到达某格子的就是最近的小偷。这和「铺瓷砖」一个原理，同时从所有源头铺，每个格子被铺到的时间就是最短距离。 “消除”不安全的格子 —— 要新建数组吗？提示说「消除所有满足 d[x][y] < v...
3699.锯齿形数组总数
3699. 锯齿形数组的总数 I原题链接 题目信息 难度：算术评级 8（偏难） 标签：动态规划、前缀和、后缀和、滚动数组 第 469 场周赛 Q3 题目理解给定 n、l、r，求长度为 n 的锯齿形数组总数。锯齿形数组需要满足： 每个元素取值 [l, r] 相邻元素不等 任意连续三个不能严格递增或严格递减 条件 3 意味着序列的方向必须交替：上升后必须下降，下降后必须上升。这就是经典 zigzag 序列。 思考过程第一版：暴力 DP（超时 + 超内存）最直觉的想法：用 dp[i][dir][x] 表示长度为 i、以 x 结尾、下一步方向为 dir 的序列数。 dir = 0 → 下一步需要下降（刚刚上升过） dir = 1 → 下一步需要上升（刚刚下降过） 初始化长度为 2 的所有情况（相邻不等即可），然后三重循环向后转移： for (int x = 0; x < range; x++) { for (int y = 0; y < range; y++) { if (x != y) { ...
频率统计与平方扩展 —— 对称子集构造
频率统计 + 平方扩展 —— 对称子集构造 日期: 2026-06-27难度: Medium标签: 哈希表、贪心、数学题目链接: 3020. 子集中元素的最大数量 题目描述给一个正整数数组，选一个子集使其元素能排成 [x, x², x⁴, ..., x^k, ..., x⁴, x², x] 的对称模式，求子集的最大元素数量。 第一次思路第一眼看到提示说用 HashSet，但马上就发现不对——HashSet 去重之后丢掉了每个数出现几次的信息，而这个模式里除了中间元素出现 1 次，其他每个数都需要 2 次（左右对称各一个），所以必须用频率表。 另一个直觉是枚举所有可能的序列长度检查是否能构造，但显然不可行。 最终方案真正的突破来自两个观察： 平方增长极快——1e9 以内最多平方 5 次就到顶，所以每个起点最多扩展几步就结束了，总复杂度很安全。 对称性决定了构造方式——从最小值 x 向中间贪心扩展，每次消耗 2 个当前值，直到遇到只有 1 个的数作为中心，或到底后回退一步。 算法流程 统计频率表 freq 数字 1 单独处理：1 的平方还是 1，所以全 1 序列长度就是 1...
单调性贪心 —— 游乐设施调度
单调性贪心 —— 游乐设施调度 题目链接: Q1 / Q2日期: 2026-06-01难度: Medium标签: 贪心、单调性 题目描述两类游乐设施（陆地、水上），每类各选一个，顺序不限。每个设施有开始时间和持续时间。完成后可以立即开始下一个（如果已开放）或等待。问最早完成时间。 第一次思路（暴力 O(nm)）Q1 数据量小（n,m ≤ 100），直接双层循环枚举所有配对： int earliestFinishTime(...) { int res = INT_MAX; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 两种顺序分别算 int t1 = max(landEnd[i], waterStart[j]) + waterDuration[j]; // 先陆地后水上 int t2 = max(waterEnd[j], landStart[i]) +...
BFS和哈希表优化同值跳跃
BFS + 哈希表优化同值跳跃 日期: 2026-05-18难度**: Hard **标签: BFS、哈希表、图优化、稀疏图题目链接：LeetCode 1345. Jump Game IV 题目描述一个整数数组 arr，从下标 0 出发，每次可以： 跳到 i+1（不越界） 跳到 i-1（不越界） 跳到任意与 arr[i] 值相同的下标 求到达最后一个下标 n-1 的最少跳跃次数。 第一次思路：邻接矩阵（卡住了）第一时间想到的就是标准的 BFS 求无权图最短路径。那就先把图建出来嘛——三个规则都很清晰： 左邻居：i → i-1 右邻居：i → i+1 同值跳跃：i → j if arr[i] == arr[j] 于是写了一个两层循环去建邻接矩阵： vector<vector<int>> graph(n, vector<int>(n, -1));for (int i = 0; i < n; i++) { if (i - 1 >= 0) graph[i][i - 1] = 1; if (i + 1...
二分答案模板 —— 求最大值 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 —...
二分查找的边界陷阱 —— 左右边界写法
由一道题目所引发的对于二分查找的思考一、题目描述 给你一个下标从 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...
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...