罗罗编程学习记录
本页内容 展开查看

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、阶乘零、回文数等数学题公式与边界
  • [ ] 能写螺旋矩阵、原地旋转、生命游戏等模拟题并处理越界
  • [ ] 能实现洗牌、蓄水池、加权随机并说明等概率依据
  • [ ] 每题能报出时间、空间口径,并列边界用例