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

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 为主;复杂度标注平均/期望/最坏口径,不确定版本行为标注待确认。