02.8 贪心与技巧题
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 贪心选择性质与最优子结构、交换论证与归纳证明、贪心失败反例
- 区间调度、区间合并与插入、最少箭、会议室、区间覆盖与交集
- 任务调度冷却、截止时间收益、跳跃游戏、分发糖果、加油站、分配饼干
- 位运算:lowbit、popcount、异或消元、掩码集合、子集枚举、格雷码与陷阱
- 数学:质数与筛法、gcd/lcm、进制转换、阶乘末尾零、回文数、摩尔投票
- 模拟:螺旋矩阵、原地旋转、生命游戏、通用模拟框架与边界处理
- 随机化:Fisher-Yates 洗牌、蓄水池抽样、加权随机、拒绝采样、期望与蒙特卡洛
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.8.1 | 贪心与技巧 | 5 个子主题 100 题:贪心证明与反例、区间与调度贪心、位运算技巧、数学与模拟技巧、随机化与概率类 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.8.1.1-006 | 01 背包贪心失败反例 | 中等 | ★★★★☆ | 贪心正确性证明与反例 |
| 02.8.1.1-011 | 区间调度按结束时间证明 | 中等 | ★★★★★ | 贪心正确性证明与反例 |
| 02.8.1.2-001 | 最多不重叠区间 | 中等 | ★★★★★ | 区间与调度贪心 |
| 02.8.1.2-002 | 合并重叠区间 | 中等 | ★★★★★ | 区间与调度贪心 |
| 02.8.1.2-004 | 最少箭引爆气球(LC 452) | 中等 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.2-005 | 会议室最大并行数 | 中等 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.2-009 | 任务调度器(LC 621) | 中等 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.2-012 | 跳跃游戏 II 最少次数(LC 45) | 中等 | ★★★★★ | 区间与调度贪心 |
| 02.8.1.2-013 | 分发糖果(LC 135) | 困难 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.2-014 | 加油站(LC 134) | 中等 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.2-017 | 划分字母区间(LC 763) | 中等 | ★★★★☆ | 区间与调度贪心 |
| 02.8.1.3-002 | n & (n-1) 清最低位 1 |
简单 | ★★★★★ | 位运算技巧 |
| 02.8.1.3-006 | 异或找唯一出现一次的数(LC 136) | 简单 | ★★★★★ | 位运算技巧 |
| 02.8.1.3-012 | 子集位掩码枚举 | 中等 | ★★★★☆ | 位运算技巧 |
| 02.8.1.3-020 | 比特位计数(LC 338) | 简单 | ★★★★☆ | 位运算技巧 |
| 02.8.1.4-006 | 阶乘末尾零(LC 172) | 中等 | ★★★☆☆ | 数学与模拟技巧 |
| 02.8.1.4-010 | 多数元素摩尔投票(LC 169) | 简单 | ★★★★☆ | 数学与模拟技巧 |
| 02.8.1.4-012 | 螺旋矩阵遍历(LC 54) | 中等 | ★★★★★ | 数学与模拟技巧 |
| 02.8.1.4-014 | 生命游戏原地更新(LC 289) | 中等 | ★★★☆☆ | 数学与模拟技巧 |
| 02.8.1.5-003 | Fisher-Yates 洗牌 | 中等 | ★★★★☆ | 随机化与概率类 |
| 02.8.1.5-005 | 蓄水池抽样 | 中等 | ★★★★☆ | 随机化与概率类 |
| 02.8.1.5-007 | 加权随机抽样 | 中等 | ★★★★☆ | 随机化与概率类 |
| 02.8.1.5-016 | 拒绝采样(LC 470) | 中等 | ★★★☆☆ | 随机化与概率类 |
当前状态
- 02.8.1 已完成 5 个子主题、100 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;复杂度标注平均/期望/最坏口径,不确定版本行为标注待确认。