02.8.1 贪心与技巧
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题
这个知识域解决什么问题
贪心策略证明、区间调度、位运算、数学模拟与随机概率五类技巧题。主线:贪心正确性证明与反例 → 区间与调度贪心 → 位运算技巧 → 数学与模拟技巧 → 随机化与概率类;每题先讲清策略依据与复杂度口径,再给可运行代码与边界用例。
知识地图
贪心正确性证明与反例(1)
→ 区间与调度贪心(2)
→ 位运算技巧(3)
→ 数学与模拟技巧(4)
→ 随机化与概率类(5)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.8.1.1 | 贪心正确性证明与反例 | 贪心与 DP 区别、交换论证、归纳证明、选择性质与最优子结构、01 背包/找零反例、常见失效来源 | 20 |
| 02.8.1.2 | 区间与调度贪心 | 区间调度、合并、插入、箭爆气球、会议室、覆盖、交集、任务调度、跳跃游戏、分发糖果、加油站 | 20 |
| 02.8.1.3 | 位运算技巧 | 与或异或移位、lowbit、2 的幂、popcount、异或找孤数、掩码集合、子集枚举、格雷码、溢出与陷阱 | 20 |
| 02.8.1.4 | 数学与模拟技巧 | 质数与筛法、gcd/lcm、进制转换、阶乘零、回文数、摩尔投票、螺旋矩阵、旋转矩阵、生命游戏、模拟框架 | 20 |
| 02.8.1.5 | 随机化与概率类 | Fisher-Yates 洗牌、蓄水池抽样、加权随机、拒绝采样、期望线性性、蒙特卡洛、随机快排、可复现测试 | 20 |
合计 100 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 建立贪心证明与反例判断能力,再 2 落地区间调度模板,3 掌握位运算常用套路,4 熟悉数学与模拟题框架,最后 5 理解随机抽样与概率分析。
自检
- [ ] 能用交换论证/归纳说明贪心不劣性,并举出贪心失败反例
- [ ] 能按目标选对区间排序键,写出调度/合并/覆盖/交集模板
- [ ] 能手写 lowbit、popcount、异或找孤数、掩码集合与子集枚举
- [ ] 能判断质数、gcd、阶乘零、回文数等数学题公式与边界
- [ ] 能写螺旋矩阵、原地旋转、生命游戏等模拟题并处理越界
- [ ] 能实现洗牌、蓄水池、加权随机并说明等概率依据
- [ ] 每题能报出时间、空间口径,并列边界用例