力扣周赛分治题判断思路:拆解子问题与合并贡献
力扣周赛最考验人的地方不是会不会某个算法而是能不能在有限时间内正确判断“这题该用什么思路”。第 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) 的时间合并出来三个都满足分治基本可行。第一个不满足说明问题有全局依赖可能更适合贪心、图遍历、最短路或差分。第二个不满足说明答案不是

相关新闻

ArkTS+AGC构建鸿蒙记账应用:从架构设计到云函数集成的实战笔记

ArkTS+AGC构建鸿蒙记账应用:从架构设计到云函数集成的实战笔记

简介:本资源是一套基于HarmonyOS生态的ArkTS语言实战项目——网吧会员终端应用,面向鸿蒙应用开发者、高校移动开发学习者及转岗工程师,解决从零构建完整商用级鸿蒙应用的核心能力训练问题。项目覆盖引导页、登录注册、密码管理、网吧浏览、会…

2026/10/25 13:16:40 阅读更多 →
Python入门必看:环境配置、VSCode搭建与turtle绘图实战

Python入门必看:环境配置、VSCode搭建与turtle绘图实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/19 7:50:34 阅读更多 →
华为手机打小字全攻略:从系统设置到Unicode特殊字符

华为手机打小字全攻略:从系统设置到Unicode特殊字符

华为手机怎么打小字?这个问题看起来简单,但真折腾起来人不少。有人是想把手机系统字体调小,有人是想在微信昵称、个性签名、群公告里输入一行“小小的字”,还有人是在备忘录里排版时要把某段文字缩小。不同需求对应不同做法&#…

2026/10/26 12:50:21 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻