力扣周赛 514 赛后讨论里出现频率最高的一个词不是“难”而是“卡”。很多人反映前两题能快速过第三题开始思路一顿第四题更难找到切入点。如果你也有类似感受我的建议是把复盘思路换一个角度不按题目顺序复盘而是按算法思想复盘先从分治出发。分治思想的价值不在“会不会背模板”而在拿到一道新题时能快速把大问题切成小问题再把小问题的结果合并成答案。力扣周赛的很多中等题和困难题表面上是区间查询、排序统计、树形递归底层几乎都能用分治的思路重新解释一遍。本文就以周赛 514 为背景整理一套可以直接照做的分治解题方案从题型识别、复杂度推导、代码模板到常见跳坑点和赛后复盘方法。文章不会逐题抄题面因为那样只能帮你记住一道题本文会尽量把“可以用分治思维切入”的题目类型抽象成模板让你下次遇到相似结构时能直接套。不管你是在准备校招笔试还是想给周赛成绩提个档这套流程都适用。1. 周赛 514 分治解题核心能力速览先给一张速览表把本场复盘需要关注的要素列清楚。能力项说明核心思想分治拆解、求解、合并覆盖题型区间统计、逆序对类、二分答案类、树形递归类常用复杂度O(n log n)、O(n)、O(log n) 需要能现场计算代码模板归并式分治、二分答案 check 函数、树形后序合并调试重点合并逻辑、边界条件、递归深度、二分死循环参考题型力扣热题 100 中的分治/二分题、历史周赛困难题本场定位从分治出发重新组织周赛 514 的复盘路径这张表是整套方法的索引。后面每一节都会围绕表格里的某一列展开。比如第 4 节讲题型识别第 5 节给归并式分治模板第 6 节给二分答案模板第 10 节给排查方法。先把表格保存在脑子里读题时逐条对照基本不会跑偏。2. 周赛为什么频繁考分治先回答一个更基本的问题为什么周赛里分治思想出现频率这么高因为分治不是某个具体数据结构而是一种组织思路。计算机能处理大规模数据靠的就是把一个大问题拆成互不重叠的小块逐块解决再合并结果。归并排序是这种思路最经典的体现快速排序也是线段树和树状数组的区间查询本质上也承载了分治思想只是把“切分”变成了“按区间分段维护”。力扣的难度设计同样遵循这个规律。简单题主要考“能不能读懂题意能不能把循环写对”中等题开始考“能不能把一个 n 的问题降到 log n 或 n log n”困难题往往不只是考一个算法而是“分治 另一个东西”的组合。比如“分治 贪心”、“二分答案 前缀和”、“树形递归 哈希表计数”。所以如果你只会单一模板遇到组合题就会卡。还有一点容易被忽视分治和二分是不同层级的概念。二分本身依赖序列的单调性而分治不依赖单调性它依赖的是“问题结构可以拆”。周赛里很多题目第一反应是二分但真正难的是 check 函数怎么写而 check 函数内部经常又是一个分治问题。从分治出发去理解就能把这两层关系理顺。3. 从数据范围反推分治复杂度周赛里最实用的能力之一是拿到题先看数据范围反推允许的时间复杂度。这个习惯能帮你快速排除错误算法。经验规则大致如下n 10^3O(n^2) 级别的算法可以接受暴力加优化通常能过。n 10^5必须考虑 O(n log n) 或 O(n)归并式分治、二分答案、线段树都在这个区间。n 10^6基本指向 O(n)要设法把分治的合并步骤做成线性。分治算法的复杂度分析可以直接套主定理。设问题规模为 n每层分成 a 个子问题每个子问题规模为 n/b合并代价为 f(n)那么 T(n) a*T(n/b) f(n)。对最常见的几种形态递推式复杂度典型场景T(n) T(n/2) O(1)O(log n)二分查找T(n) 2*T(n/2) O(n)O(n log n)归并排序、逆序对统计T(n) T(n/2) O(n)O(n)快速选择类题目T(n) 2*T(n/2) O(n^2)O(n^2)某些区间 DP 的暴力版本有时候周赛 TLE 不是代码写得慢而是选错了分治策略。比如 n 10^5 的时候O(n^2) 的区间 DP 明显不可行就应该转向“分治 合并计数”或者“二分答案”。反过来n 10^3 时直接写分治也可能因为常数太大而超时此时暴力模拟反而更稳。4. 周赛分治题型识别清单拿到一道题怎么判断它是不是分治题下面这张清单是我比较常用的判断依据按重要性排序。第一能不能把区间按中点切开。如果问题与顺序无关只看元素之间的大小关系通常可以先排序再用分治。第二左右两边是否各自独立。如果左半部分的答案不受右半部分影响只有合并时需要跨区间信息这就是典型的分治结构。第三合并时是否需要统计“跨区间贡献”。逆序对、区间内满足大小关系的数对、排序后区间合并都属于这一类。第四是否存在“可行 / 不可行”的单调性。如果答案是“最大值的最小值”或“最小值的最大值”优先考虑二分答案。第五树形结构问题。树的遍历天然是分治分别处理左右子树再在当前节点合并。我把这些特征整理成一张速查表写题前扫一眼能节约不少时间。题型特征优先考虑的分治方案区间查询 单点修改线段树分治思想的区间形态统计跨区间数对归并式分治最大化最小值 / 最小化最大值二分答案 贪心 check树形依赖、子树合并后序遍历分治第 K 大 / 第 K 小快速选择或二分答案这套清单不能保证覆盖所有题但能覆盖周赛里绝大多数分治类考法。如果你发现一道题既不能排序后拆区间也没有单调性也没有树形结构那大概率不是分治题别硬套。5. 归并式分治模板适用于跨区间统计周赛里最常见的分治题是“统计满足某种条件的数对”。这类题的关键点在于不能暴力两层循环复杂度 O(n^2) 在 n10^5 时直接爆炸。正确思路是用归并式分治把数对分成三类左半内部、右半内部、跨左右前两类递归解决第三类在合并时统一统计。下面是一份统计逆序对的 Python 模板。逆序对是最经典的代表题理解它之后很多类似题目只需要改合并时的判断条件。def merge_sort_count(nums, left, right): if left right: return 0 mid (left right) // 2 cnt merge_sort_count(nums, left, mid) merge_sort_count(nums, mid 1, right) temp [] i, j left, mid 1 while i mid and j right: if nums[i] nums[j]: temp.append(nums[i]) i 1 else: cnt mid - i 1 temp.append(nums[j]) j 1 while i mid: temp.append(nums[i]) i 1 while j right: temp.append(nums[j]) j 1 nums[left:right 1] temp return cnt使用时先复制一份 nums再调用函数避免原数组被破坏。这个模板的核心只有两个动作左半递归统计合并时统计跨区间贡献。这类模板在周赛中的变化主要有三种改成统计 nums[i] 2 * nums[j] 的翻转对只需要把合并时的条件从nums[i] nums[j]换成nums[i] 2 * nums[j]。改成统计降序数对只要把比较符号反过来。改成统计区间和差值合并时先处理前缀和。注意合并统计时千万不要用全局变量保存 cnt否则在多组测试数据下会累积错误结果。推荐在递归函数内部返回计数这样逻辑更干净。6. 二分答案式分治适用于可行性与最值问题第二种高频分治模板是二分答案。严格来说二分是更简单的单侧分治每次把搜索区间切成两半根据判断结果决定保留哪一半。周赛题目里只要出现“最大化最小值”或“最小化最大值”的描述基本可以确定要用二分答案。核心工作是写一个 check(mid) 函数判断“在当前限制 mid 下能否完成任务”。如果 check 满足单调性也就是 mid 越大越可能满足或者 mid 越大越不可能满足就可以二分。下面是一个最小化最大值的通用模板以“将数组分成 m 段使得各段和的最大值最小”为例。def can_split(nums, m, limit): cnt 1 cur 0 for x in nums: if cur x limit: cnt 1 cur x else: cur x return cnt m def split_array_minimize_max(nums, m): left max(nums) right sum(nums) while left right: mid (left right) // 2 if can_split(nums, m, mid): right mid else: left mid 1 return left这段模板的关键在边界更新满足条件时保留 mid不满足时排除 mid。写完 check 之后最好先用三个小用例验证一、m1 时答案是整个数组的和二、mlen(nums) 时答案是数组最大值三、数组全相等时答案是否正常。二分答案的一个常见变形是“二分时间”。例如机器人搬货物、任务调度、订单处理这类题给定一个时间上限判断在时间上限内能否完成然后在时间上二分。和直接的数值二分相比只是 check 函数里的逻辑从“分割段”换成了“模拟调度”模板本身不用改。7. 树形递归与树分治适用于子树合并问题周赛里第三类分治题出现在树上。树的递归天然契合分治思想一棵树由左子树和右子树组成先递归拿到子树的答案再在当前节点合并。比较常见的套路是后序遍历。设计递归函数时返回值不只是当前子树的一个结果而是包含多个统计信息。例如某些题目需要同时知道子树的高度、节点数、最大路径和这时可以返回一个小对象或小元组。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def dfs(root): # 返回三个值子树高度、子树内最优路径和、以当前节点为起点的最大链和 if not root: return (0, -10**9, -10**9) left_h, left_best, left_sum dfs(root.left) right_h, right_best, right_sum dfs(root.right) h max(left_h, right_h) 1 best max(left_best, right_best, right_sum root.val left_sum) cur_sum max(left_sum, right_sum, 0) root.val return (h, best, cur_sum)这个模式在“二叉树的最大路径和”“树的直径”等题目里反复使用。写树形递归时最容易踩的坑是只处理了空节点但没有处理单边节点为空的情况。比如左子树为空时left_best 和 left_sum 要设置成不影响结果的值而不是 0。具体设置什么值取决于题目允许路径能否经过空节点。另一个坑是 Python 的默认递归深度。力扣 Python3 环境递归深度默认在 1000 左右对于链状树栈深度会直接超限。建议在周赛环境里可以在代码开头加上import sys; sys.setrecursionlimit(10**6)。如果题目明确限制不能递归就要考虑显式栈迭代写法。8. 复盘周赛 514 的实战流程说了这么多模板回到周赛 514 本身。我的建议是不复盘具体题号而是复盘“拿到题之后的三分钟决策”。这是比 AC 数量更重要的能力。拿到四道题后先花 30 秒读数据范围把每道题的可接受复杂度写在题目旁边。这一步能过滤掉一半错误思路。比如某题 n 到 10^5那么任何 O(n^2) 的写法都别碰某题 n 最多 10^3反而可以先用暴力确认正确性再考虑是否优化。然后按难度分层处理。前两道题先跑通暴力解保证基础分拿到。第三道题如果一眼没有模拟方案优先检查是不是分治结构能不能排序后统计跨区间能不能二分答案。第四道题更倾向于分治与贪心的组合先想清楚“能不能切开题目给出的结构”每个子问题是否独立。写完代码后不要急着提交先手跑三个小用例最小规模用例、全相等用例、边界用例。对分治代码来说重点检查合并时左右区间是否重复计算递归终止条件是否正确二分更新语句是否会死循环。这三个点占周赛 WA 的大头。赛后复盘时把每道题按失败原因分类是“没识别出分治”还是“识别出但模板不熟”或者是“模板对了但边界写错”。分类越细下一次训练越有针对性。9. 在力扣刷题体系中补齐分治能力如果你分治基础薄弱不建议直接从周赛困难题开始硬磨。更稳妥的顺序是先把力扣热题 100 中与排序、二分、树相关的题目做完再做专门的 tag 练习最后回到周赛实战验证。9.1 先说刷题顺序力扣热题 100 里有很多分治思想的载体题。最大子数组和可以用分治解也可以 DP 解两种解法对比之后会更容易理解“分治的合并步骤到底在算什么”。数组中的逆序对、排序数组、搜索旋转排序数组分别对应归并式分治和二分查找式分治。专门练习分治时不要只挑简单题。归并排序、快速排序、第 K 大元素、有序矩阵第 K 小这些题能训练“递归分层 归并逻辑”的直觉。等模板熟练之后再去做带二分答案的题比如“分割数组的最大值”这类最小化最大值问题你会发现自己能更快写出 check 函数。9.2 再说题型分类周赛历史题目同样值得专门复盘。早一些的周赛困难题难度系数虽然高但题型更“正”很适合用来训练分治识别能力。比如周赛 430 的困难题如果当时没 AC赛后可以按“分治模板 复杂度分析”重写一遍而不是只看题解然后复制。值得提醒的是力扣题分类不只分治一种。比如“腐烂的橘子”这类网格题实际上是多源 BFS不属于分治但经常有人混在一起刷。原因在于题型分类比单题更重要你先判断这是图遍历还是分治统计再决定用什么模板。能做对这道分类判断刷题效率会明显提升。9.3 周赛复盘习惯每次周赛结束后给自己留 30 分钟专门做复盘。复盘不是看一遍题解而是要用自己的话写出四件事每道题属于什么题型数据范围能承受什么复杂度核心解法用到了哪个模板错误发生在哪个环节。如果一道题你最终是靠别人题解做出来的建议第二天不看题解重写一遍。重写时不要复制粘贴而是把模板从记忆里调出来再针对题目调整边界条件。这个过程比连续刷五道同类题更有效。10. 常见错误与排查方法这里整理一张排查表覆盖周赛里最常见的问题。遇到 WA 或 TLE 时按表格顺序检查多数问题能定位。问题现象可能原因排查方式解决方案递归栈溢出递归深度过大打印递归层数观察设置递归上限或改迭代合并统计重复计算跨区间贡献被左右两侧重复算打印合并时区间范围明确左右区间边界统一闭区间二分死循环mid 更新公式与 left/right 关系矛盾用 l1,r2 手推几步leftmid1 或 rightmid 保持单调收缩TLE复杂度高于数据范围要求计算主定理递推式改成 O(n log n) 分治或二分答案WA 边界用例数组长度为 1 或全部相等补小用例测试在递归入口加空数组判断变量污染递归函数共用全局数组检查递归中是否修改原数组使用局部拷贝或返回新数组分治代码调试时我比较推荐“对拍”的方法。写一个暴力解再写一个分治解用随机小数据反复对比结果。import random def brute(nums): ans 0 n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j]: ans 1 return ans def divide(nums): # 调用第 5 节模板 nums nums[:] return merge_sort_count(nums, 0, len(nums) - 1) for _ in range(10000): nums [random.randint(0, 10) for _ in range(random.randint(0, 10))] if brute(nums) ! divide(nums): print(mismatch, nums) break else: print(all ok)对拍通过后可以说明算法核心逻辑没有大问题剩下再检查性能和边界。11. 最佳实践与周赛使用建议最后给几条和周赛实战强相关的建议。第一先暴力后优化。周赛里前三题往往存在暴力解先用暴力把题目理解透再写分治优化比直接上手最优解更稳。暴力解还能用来生成对拍数据。第二写代码前把递归边界和合并规则写在注释里。很多 WA 是合并时忘了把两侧结果加起来或者边界条件写反。把规则写下来相当于一次代码 review。第三注意变量的可变性。分治递归中尽量不用全局计数器和全局数组用函数返回值传递状态。这样能避免多组测试之间互相污染也让代码更容易 debug。第四如果提交后 TLE第一件事不是改常数而是重新判断复杂度。先确认数据范围下 O(n log n) 是不是真的可行如果数据已经是 10^5 级别递归的 log 层也会带来不小的栈和调用开销此时可以考虑用迭代式归并或直接排序处理。第五合规与工程习惯。刷题本身不存在版权问题但如果你把周赛题解发布到自己的仓库或博客不要直接复制官方或他人的完整题解尽量用自己的模板和思路重写涉及公司笔试题库时要注意保密协议。12. 总结周赛 514 最值得复盘的不是某道题的 AC 代码而是从分治出发的整套思考方式识别题型、反推复杂度、套模板、写 check、排查边界。建议你先做三件事把第 5 节的归并模板在本地跑通把第 6 节的二分模板至少改造成一道你熟悉的新题下一次周赛开赛前用第 4 节的识别清单把四道题各分类一次。这三件事做完你对分治的掌控会比刷十道题更扎实。最容易踩的三个坑也再强调一遍合并时重复计算、二分死循环、递归深度超限。这三个坑对应解决三件事写递归函数时明确定义区间写二分时手推 l1、r2 的小例子写树题时主动 setrecursionlimit。这篇文章可以直接收藏作为你下一场周赛开赛前 10 分钟的快速检查清单。下次拿到题目如果思路卡住先把“能不能分治、能不能二分、能不能归并合并”这三个问题过一遍大概率能找到出口。