跳到主要内容

算法总结

· 阅读需 4 分钟
Eureka X
Eureka X
Mr.Nobody

记录做力扣面试经典150过程中遇到的算法🤔​

贪心算法​

🎯 识别贪心算法适用场景的技巧​

1. 问题特征识别​

以下特征通常表明可以使用贪心算法：

✅ 最优子结构：问题的最优解包含子问题的最优解 ✅ 贪心选择性质：局部最优选择能导致全局最优 ✅ 无后效性：当前选择不会影响之前的状态 ✅ 求极值问题：最大值、最小值、最优解等

2. 常见问题类型​

以下类型问题经常使用贪心策略：

🔢 选择问题：活动选择、区间调度 💰 优化问题：背包问题变种、股票买卖 🗺️ 图论问题：最小生成树、最短路径 📊 数据处理：哈夫曼编码、任务调度 🎯 游戏策略：跳跃游戏、分配问题

🎯 如何快速判断的技巧​

技巧1：问自己几个关键问题​

  1. 是否可以通过一系列局部选择得到全局最优解？
  2. 当前的最优选择是否会影响后续的决策空间？
  3. 如果每步都选当前最好的，最终结果是否最优？
  4. 是否存在反例能证明贪心不成立？

技巧2：看问题的关键词​

出现这些关键词时考虑贪心：

  • "最大"、"最小"、"最优"
  • "尽可能"、"最多"、"最少"
  • "安排"、"调度"、"分配"
  • "使得总...最大/最小"

🎯 如何设计贪心策略​

1. 确定贪心选择标准​

关键步骤：

  1. 明确每一步要做出什么选择
  2. 确定衡量"好"选择的标准
  3. 证明这个选择标准的正确性

2. 举例分析​

股票买卖问题分析：

  • 问题：如何获得最大利润？
  • 贪心选择：只要明天比今天贵，今天就买入明天卖出
  • 选择标准：价格正增长就交易
  • 正确性：所有正收益都 captured，负收益都避免

跳跃游戏问题分析：

  • 问题：能否到达终点？
  • 贪心选择：每到一个位置，尽可能扩展可达范围
  • 选择标准：选择能让maxReach最大的策略
  • 正确性：最大可达范围决定了能否到达终点

🎯 实战判断流程​

三步判断法：​

Step 1: 问题分析

  • 这是一个优化问题吗？(求最大/最小值)
  • 是否可以分解为一系列选择？

Step 2: 贪心假设

  • 能否通过局部最优选择得到全局最优？
  • 假设贪心策略，能否构造反例？

Step 3: 策略设计

  • 明确每步的贪心选择是什么
  • 确定如何衡量选择的好坏
  • 验证算法正确性

🎯 常见贪心策略模板​

1. 选择类问题​

// 模板：按某种标准排序后贪心选择
sort(elements, compare_function);  // 首先按某种标准排序
for (each element) {               // 遍历每个元素
    if (can_select(element)) {     // 如果可以选择当前元素
        select(element);           // 就选择它
    }
}

2. 扩展类问题​

// 模板：逐步扩展最优解
for (each step) {                           // 遍历每个决策步骤
    best_choice = find_best_local_choice(); // 在当前步骤中找到局部最优选择
    if (is_better(best_choice)) {           // 如果这个选择比当前解更好
        update_solution(best_choice);       // 就用这个选择更新当前最优解
    }
}

3. 累积类问题​

// 模板：累积局部最优解
total_result = 0;                    // 初始化总结果为0
for (each sub_problem) {             // 遍历每个子问题
    local_optimal = solve_locally(); // 求解当前子问题的局部最优解
    total_result += local_optimal;   // 将局部最优解累加到总结果中
}

💡 实用建议​

  • 多练习经典贪心问题：活动选择、背包问题、霍夫曼编码等
  • 学会构造反例：如果想不出反例证明贪心成立
  • 关注边界条件：贪心算法常在边界处出错
  • 证明贪心选择性质：虽然面试不要求严格证明，但思路要清晰

记住：贪心算法的关键在于识别问题的贪心性质和设计正确的贪心策略，这需要大量的练习和经验积累。

加载评论中...