把每日大赛91从头捋一遍：思路换一下就通更稳，分歧怎么来的，你会发现完全不一样
导语 每次赛后回看，总会觉得当时卡住的地方其实并不难。关键在于看问题的角度。把每日大赛91从头捋一遍，不只是复盘答案，更要换一种思路去理解题目、构造不易出错的解法，知道为什么不同人的实现会完全不一样——那往往源于对约束、等价转换或边界的不同理解。下面用三类典型题目拆解思路变化、常见分歧来源，以及实操细节，帮助你在下一次比赛里更稳更快。
一、赛前读题的三步“核查法” 1) 把输入输出以及限制明确写出（n 的大小、数值范围、是否有负数等）。 2) 找出能写成小例子的最简单情形，暴力求解并手推一遍。 3) 列出题目允许的时间/空间上界，判断是否要优化到 O(n)、O(n log n) 还是可以接受 O(n^2)。
二、思路切换的常见技巧（核心心法）
- 从构造到计数/判定：很多构造类题可以反过来考虑“可能性”而不是逐步构造。例如不直接构造数组，而是判断是否存在满足约束的计数分配。
- 逆向思考：从终态往前推，往往能找到不易察觉的约束关系或不变元。
- 把操作看成图的边或状态转移：复杂的局部操作有时等价于图上的路径问题或并查集合并。
- 等价变换：把问题变成熟悉的模板（前缀和、滑动窗口、二分可行性、单调栈、贪心证明）。
- 减法优于加法：构造时常从某一极端开始减去不合法部分，比从零开始构造更容易控制边界。
三、逐题捋一遍（以三类代表题目为例）
题目 A（容易，字符串/计数型） 题目示例：给定字符串 s，只含小写字母。问能否通过最多 k 次字符替换使得字符串中存在长度为 m 的子串，子串中所有字符相同。
直觉一：枚举子串，统计每种字符的频率，判断需要替换的次数是否 ≤ k。复杂度 O(26·n) 可行。
更稳的变换：滑动窗口 + 维持窗口中某字符的最大频率 maxFreq。窗口长度为 m 时，所需替换数 = m - maxFreq。直接维护 maxFreq 可以用 26 长度的计数器或单字符频率数组更新，复杂度 O(n)。
实现要点：
- 当 m 很大（接近 n）时注意边界处理。
- maxFreq 的维护可在每次右指针移动时更新，不需要每次扫描 26 次（还是可以接受但在超大字符集时要优化）。
题目 B（中等，前缀和/哈希） 题目示例：给定数组 nums，长度 n（含正负数），问有多少对 (i, j)（i < j）使得子数组 i..j 的和为 target。
直觉一：前缀和 + 哈希表。遍历前缀和 pref，计数出现过 pref - target 的频次。
细节与陷阱：
- 使用 64 位整数防止溢出（特别是数值范围大时）。
- 若题目要求子数组数量巨大，结果可能需要取模。
- 若含浮点数，哈希不可直接用浮点做键，需离散化或转成分数形式。
伪代码（Python 风格）： count = 0 hash = {0:1} pref = 0 for x in nums: pref += x count += hash.get(pref - target, 0) hash[pref] = hash.get(pref, 0) + 1
题目 C（困难，贪心+二分/DP） 题目示例：有 n 个任务，每个任务有耗时和截止时间，最多能同时做一个任务，问最多能完成多少任务（或最小延迟总和）。
两种常见解法对比：
- 贪心+堆：按截止时间排序，依次尝试加入任务，总时间超过当前任务的截止时，从已选任务中剔除耗时最长的。复杂度 O(n log n)。
- DP（当 n 小或有额外结构时）：对耗时或截止做状态压缩/二分优化。
为什么两种实现差别大？
- 贪心的正确性需证明：每次遇到超时，剔除最长任务不会降低最终可完成任务数，这来自于交换论证。
- DP 更直观但易超时、容易出错在状态边界和初始化。
四、分歧从哪来？（常见源头）
- 约束理解不同：是否含等号、是否允许空子串/空解、索引从 0 还是 1 起；这些小差异会导致完全不同的边界处理。
- 优化路径不同：有人先想贪心，有人先想 DP；对某些数据分布贪心简洁且更快，但若忘了证明可行性就容易错。
- 数据类型与溢出处理：整数溢出、浮点精度、模运算等会带来不同结果。
- 初始条件与边界：是否需要初始化哈希表的 0：1，是否处理空数组，是否处理单元素情况。
- 细节实现差异：排序是否稳定、在并查集中是否路径压缩、队列中元素出入顺序等。
五、如何把思路换得更“通更稳” 1) 写出小例子并暴力验证：先用暴力方法写一个生成器测试，然后用更优方法与之对比。 2) 找不变量：操作前后有哪些量不变？它们常是正确性证明的关键。 3) 先证明可行性，再写代码：遇到贪心策略时，草稿上写出交换论证或反证。 4) 把边界拆出来专门测试：n=0、n=1、所有数相同、升序/降序等。 5) 写测试用例脚本做穷举或随机检测（尤其在比赛后复盘时）。
六、复盘清单（快速自检）
- 我是否把题目的所有限制都列清楚了？
- 有没有把题目化成已知模板？
- 我的解法时间/空间是否在允许范围？
- 是否写了关键边界的手工例子并通过？
- 是否有可构建的反例能打败我的策略？
结语 捋题不是把答案背下来，而是训练看题的“视角转换能力”。同一道题，换个观察角度，往往能把复杂的状态压成简单的不变量，把模糊的贪心变成可证明的策略。把每日大赛91当作练习场：每道题不只写一次解法，而要试着找 2–3 种思路，比较它们的边界行为和复杂度，这样下次面对新题时，你会更快看到那条“更稳”的路。有什么具体题目想一起深挖，贴题目我帮你逐题拆到位。
