力扣周赛分治题判断思路：拆解子问题与合并贡献

力扣周赛最考验人的地方不是会不会某个算法而是能不能在有限时间内正确判断“这题该用什么思路”。第 514 场周赛我拿到题目之后没有急着写代码而是先把四道题都按分治的角度过了一遍能不能对半拆拆完能不能直接合并跨过中点的贡献要不要单独补算。这里不刻意还原原题逐字描述赛后官方题解会讲得更细我更想聊的是分治这条线上周赛题常见的几种形态以及我平时怎么判断、怎么写、怎么排错。不管你是刚打完 514还是回头补 430这套判断流程都能直接用。1. 分治在周赛里往往不是“一眼分治”1.1 分治的本质是“拆得开、合得起”分治的流程表面上只有三步分解、解决、合并。难点从来不在“分解”而在“合并”。很多人在周赛里卡住不是因为想不到要把数组对半分而是不知道左右两半的结果怎么合成一个答案或者忽略了跨过中点的贡献。举个例子统计数组里满足i j且nums[i] 2 * nums[j]的下标对数。表面看这不是二叉树也不是快速幂但它就是典型的分治题把数组从中间切开左边内部的下标对、右边内部的下标对递归处理跨过中点的下标对需要在合并阶段用双指针或有序性补算。能说清“左、右、跨中点”这三类贡献分别怎么算题目就已经解了一半。所以我的第一个建议是遇到疑似分治的题先逼自己说出这句话——“这道题的子问题是什么合并时哪部分贡献是新的。”说不出来说明还没真懂题意直接写代码大概率是错的。1.2 周赛里最常见的几种分治外壳分治不会直接写在题目上它往往套着不同的外壳。周赛里常见的有这几种外壳分治内核周赛常见位置二分查找、二分答案每次把问题规模折半快速排除一半空间第 2、3 题下标对 / 子数组统计左右区间内部递归跨中点贡献单独统计第 3、4 题二叉树的递归处理左右子树天然拆分结果合并到父节点第 2、3 题分治优化动态规划用分治加速部分状态转移第 4 题这里要说明一下二分查找严格来说不算分治但它的“规模减半 只处理需要的那一半”的核心思路和分治同源。周赛里经常出现先二分答案、再在 check 函数里用双指针或贪心判断的题这种题真正难的是 check不是二分本身。1.3 先能说出“子问题是什么”再谈算法写代码之前我习惯先给每道题写一句话记录子问题子问题是“左半段内部的答案”子问题是“右半段内部的答案”新增的是“跨过中点的答案”。如果第三个问题回答不出来就退回暴力思路看暴力枚举里哪些比较是多余的。能去掉重复枚举合并逻辑自然就浮现了。这个动作看着简单但能避免你在错误的算法方向上走太远。2. 判断一道题该不该用分治2.1 连问自己三个问题比赛里时间紧我一般用三个问题快速判断把输入对半拆开两半各自能不能独立算出一个局部答案全局答案是不是“左半答案 右半答案 跨中点答案”的组合跨中点的答案能不能用 O(n) 或 O(n log n) 的时间合并出来三个都满足分治基本可行。第一个不满足说明问题有全局依赖可能更适合贪心、图遍历、最短路或差分。第二个不满足说明答案不是