尧图网站建设 
一、贪心算法核心知识点1. 什么是贪心算法定义在每一步选择中都采取当前状态下最好或最优的选择从而希望导致结果是全局最优的算法。通俗理解就像吃自助餐你每次都拿最贵的菜希望最后吃回本就像找零钱每次都拿最大面额的纸币2. 贪心算法的基本要素要素说明贪心选择性质每一步的局部最优选择能导致全局最优解最优子结构问题的最优解包含子问题的最优解无后效性当前决策不影响后续决策的独立性3. 贪心 vs 动态规划对比项贪心算法动态规划决策方式每一步只做当前最优考虑所有可能选全局最优是否回溯不回溯需要回溯时间复杂度通常较低通常较高适用条件贪心选择性质 最优子结构最优子结构 重叠子问题4. 贪心算法的步骤text1. 将问题分解为若干个子问题 2. 找出贪心策略怎么选才是当前最优 3. 证明贪心策略的正确性最难 4. 实现算法二、经典贪心算法题目及代码题目1找零钱问题LeetCode 322 变种问题有面额 [1, 2, 5, 10, 20, 50, 100] 的纸币用最少的张数凑出金额 n。贪心策略优先使用大面额纸币pythondef coin_change(coins, amount): 贪心找零前提货币系统是标准的能用贪心 coins: 面额列表已从大到小排序 amount: 需要凑的金额 返回需要的纸币张数 coins.sort(reverseTrue) # 从大到小排序 count 0 remaining amount for coin in coins: if remaining 0: break # 能用几张当前面额的纸币 num remaining // coin count num remaining - num * coin print(f使用 {num} 张 {coin} 元) if remaining ! 0: return -1 # 无法凑出 return count # 测试 coins [100, 50, 20, 10, 5, 2, 1] amount 188 result coin_change(coins, amount) print(f最少需要 {result} 张纸币) # 输出使用 1 张 100元1张50元1张20元1张10元1张5元1张2元1张1元题目2活动选择问题问题给定多个活动的开始和结束时间选择最多的互不冲突的活动。贪心策略优先选择结束时间最早的活动pythondef activity_selection(activities): 活动选择问题 activities: [(开始时间, 结束时间), ...] 返回最多能选择的活动数量 if not activities: return 0 # 按结束时间排序 activities.sort(keylambda x: x[1]) count 1 # 选择第一个活动 last_end activities[0][1] # 第一个活动的结束时间 selected [activities[0]] # 记录选中的活动 for start, end in activities[1:]: if start last_end: # 下一个活动的开始 上一个活动的结束 count 1 last_end end selected.append((start, end)) print(选中的活动:, selected) return count # 测试 activities [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)] result activity_selection(activities) print(f最多能安排 {result} 个活动)题目3分发饼干LeetCode 455问题每个孩子最多只能给一块饼干。每个孩子 i 有一个胃口值 g[i]每块饼干 j 有尺寸 s[j]。当 s[j] g[i] 时孩子满足。最多能满足多少个孩子贪心策略用最小尺寸的饼干去满足最小胃口的孩子pythondef find_content_children(g, s): 分发饼干 g: 孩子的胃口值列表 s: 饼干尺寸列表 返回最多能满足的孩子数量 g.sort() s.sort() child 0 # 孩子指针 cookie 0 # 饼干指针 count 0 while child len(g) and cookie len(s): if s[cookie] g[child]: # 这块饼干能满足这个孩子 count 1 child 1 cookie 1 else: # 这块饼干太小换一块更大的 cookie 1 return count # 测试 g [1, 2, 3] # 孩子的胃口 s [1, 1] # 饼干尺寸 print(f能满足 {find_content_children(g, s)} 个孩子) # 输出: 1题目4跳跃游戏LeetCode 55问题给定一个非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。贪心策略维护能到达的最远位置pythondef can_jump(nums): 跳跃游戏 返回是否能到达最后一个位置 max_reach 0 # 当前能到达的最远位置 n len(nums) for i in range(n): # 如果当前位置已经超过了能到达的最远位置 if i max_reach: return False # 更新能到达的最远位置 max_reach max(max_reach, i nums[i]) # 如果已经能到达最后一个位置 if max_reach n - 1: return True return True # 测试 nums1 [2, 3, 1, 1, 4] nums2 [3, 2, 1, 0, 4] print(can_jump(nums1)) # True print(can_jump(nums2)) # False题目5跳跃游戏 IILeetCode 45问题跳到最后一个位置的最少跳跃次数。贪心策略在当前能到达的范围内选择能跳到最远的下一步pythondef jump(nums): 跳跃游戏 II - 最少跳跃次数 n len(nums) if n 1: return 0 jumps 0 # 跳跃次数 current_end 0 # 当前跳跃能到达的最远位置 max_reach 0 # 下一次跳跃能到达的最远位置 for i in range(n - 1): # 更新下一次能到达的最远位置 max_reach max(max_reach, i nums[i]) # 如果到达了当前跳跃的边界 if i current_end: jumps 1 current_end max_reach # 如果已经能到终点 if current_end n - 1: break return jumps # 测试 nums [2, 3, 1, 1, 4] print(f最少需要 {jump(nums)} 次跳跃) # 输出: 2题目6划分字母区间LeetCode 763问题将字符串划分为尽可能多的片段使得同一个字母最多出现在一个片段中。贪心策略记录每个字母最后出现的位置在区间内扩展右边界pythondef partition_labels(s): 划分字母区间 返回每个片段的长度列表 # 记录每个字符最后出现的位置 last_pos {} for i, char in enumerate(s): last_pos[char] i result [] start 0 end 0 for i, char in enumerate(s): # 更新当前片段的结束位置 end max(end, last_pos[char]) # 如果当前位置就是结束位置 if i end: result.append(end - start 1) start end 1 return result # 测试 s ababcbacadefegdehijhklij print(f分区长度: {partition_labels(s)}) # [9, 7, 8]题目7加油站LeetCode 134问题环形路上有 n 个加油站第 i 个加油站有 gas[i] 升汽油从 i 到 i1 需要 cost[i] 升汽油。从哪个加油站出发可以走完全程贪心策略如果总油量 总消耗一定有解从油量赤字之后的下一个位置开始pythondef can_complete_circuit(gas, cost): 加油站问题 返回起点索引如果无法走完返回 -1 total_gas 0 total_cost 0 current_gas 0 start 0 for i in range(len(gas)): total_gas gas[i] total_cost cost[i] current_gas gas[i] - cost[i] # 如果当前油量不够说明从 start 到 i 这段都不行 if current_gas 0: start i 1 current_gas 0 # 如果总油量 总消耗一定有解 return start if total_gas total_cost else -1 # 测试 gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] print(f从第 {can_complete_circuit(gas, cost)} 个加油站出发)三、贪心算法使用建议✅ 什么时候用贪心问题具有贪心选择性质问题的最优解包含子问题的最优解经典问题找零钱、活动选择、哈夫曼编码、最小生成树、最短路径(Dijkstra)❌ 什么时候不用贪心需要回溯才能找到最优解如背包问题的 0-1 版本当前选择会影响未来的选择如旅行商问题贪心能得到局部最优但不能保证全局最优四、常见题型总结类型经典题目贪心策略区间问题活动选择、无重叠区间按右端点排序分配问题分发饼干、分发糖果排序后从最小开始匹配跳跃问题跳跃游戏 I/II维护能到达的最远位置字符串处理划分字母区间、移除数字贪心选择边界数组处理加油站、股票买卖累加差值找转折点五、时间复杂度总结排序类分发饼干、活动选择O(n log n)遍历类跳跃游戏、加油站O(n)空间复杂度通常 O(1) 或 O(n) 贪心算法详情分析
一、贪心算法核心知识点1. 什么是贪心算法定义在每一步选择中都采取当前状态下最好或最优的选择从而希望导致结果是全局最优的算法。通俗理解就像吃自助餐你每次都拿最贵的菜希望最后吃回本就像找零钱每次都拿最大面额的纸币2. 贪心算法的基本要素要素说明贪心选择性质每一步的局部最优选择能导致全局最优解最优子结构问题的最优解包含子问题的最优解无后效性当前决策不影响后续决策的独立性3. 贪心 vs 动态规划对比项贪心算法动态规划决策方式每一步只做当前最优考虑所有可能选全局最优是否回溯不回溯需要回溯时间复杂度通常较低通常较高适用条件贪心选择性质 最优子结构最优子结构 重叠子问题4. 贪心算法的步骤text1. 将问题分解为若干个子问题 2. 找出贪心策略怎么选才是当前最优 3. 证明贪心策略的正确性最难 4. 实现算法二、经典贪心算法题目及代码题目1找零钱问题LeetCode 322 变种问题有面额 [1, 2, 5, 10, 20, 50, 100] 的纸币用最少的张数凑出金额 n。贪心策略优先使用大面额纸币pythondef coin_change(coins, amount): 贪心找零前提货币系统是标准的能用贪心 coins: 面额列表已从大到小排序 amount: 需要凑的金额 返回需要的纸币张数 coins.sort(reverseTrue) # 从大到小排序 count 0 remaining amount for coin in coins: if remaining 0: break # 能用几张当前面额的纸币 num remaining // coin count num remaining - num * coin print(f使用 {num} 张 {coin} 元) if remaining ! 0: return -1 # 无法凑出 return count # 测试 coins [100, 50, 20, 10, 5, 2, 1] amount 188 result coin_change(coins, amount) print(f最少需要 {result} 张纸币) # 输出使用 1 张 100元1张50元1张20元1张10元1张5元1张2元1张1元题目2活动选择问题问题给定多个活动的开始和结束时间选择最多的互不冲突的活动。贪心策略优先选择结束时间最早的活动pythondef activity_selection(activities): 活动选择问题 activities: [(开始时间, 结束时间), ...] 返回最多能选择的活动数量 if not activities: return 0 # 按结束时间排序 activities.sort(keylambda x: x[1]) count 1 # 选择第一个活动 last_end activities[0][1] # 第一个活动的结束时间 selected [activities[0]] # 记录选中的活动 for start, end in activities[1:]: if start last_end: # 下一个活动的开始 上一个活动的结束 count 1 last_end end selected.append((start, end)) print(选中的活动:, selected) return count # 测试 activities [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)] result activity_selection(activities) print(f最多能安排 {result} 个活动)题目3分发饼干LeetCode 455问题每个孩子最多只能给一块饼干。每个孩子 i 有一个胃口值 g[i]每块饼干 j 有尺寸 s[j]。当 s[j] g[i] 时孩子满足。最多能满足多少个孩子贪心策略用最小尺寸的饼干去满足最小胃口的孩子pythondef find_content_children(g, s): 分发饼干 g: 孩子的胃口值列表 s: 饼干尺寸列表 返回最多能满足的孩子数量 g.sort() s.sort() child 0 # 孩子指针 cookie 0 # 饼干指针 count 0 while child len(g) and cookie len(s): if s[cookie] g[child]: # 这块饼干能满足这个孩子 count 1 child 1 cookie 1 else: # 这块饼干太小换一块更大的 cookie 1 return count # 测试 g [1, 2, 3] # 孩子的胃口 s [1, 1] # 饼干尺寸 print(f能满足 {find_content_children(g, s)} 个孩子) # 输出: 1题目4跳跃游戏LeetCode 55问题给定一个非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。贪心策略维护能到达的最远位置pythondef can_jump(nums): 跳跃游戏 返回是否能到达最后一个位置 max_reach 0 # 当前能到达的最远位置 n len(nums) for i in range(n): # 如果当前位置已经超过了能到达的最远位置 if i max_reach: return False # 更新能到达的最远位置 max_reach max(max_reach, i nums[i]) # 如果已经能到达最后一个位置 if max_reach n - 1: return True return True # 测试 nums1 [2, 3, 1, 1, 4] nums2 [3, 2, 1, 0, 4] print(can_jump(nums1)) # True print(can_jump(nums2)) # False题目5跳跃游戏 IILeetCode 45问题跳到最后一个位置的最少跳跃次数。贪心策略在当前能到达的范围内选择能跳到最远的下一步pythondef jump(nums): 跳跃游戏 II - 最少跳跃次数 n len(nums) if n 1: return 0 jumps 0 # 跳跃次数 current_end 0 # 当前跳跃能到达的最远位置 max_reach 0 # 下一次跳跃能到达的最远位置 for i in range(n - 1): # 更新下一次能到达的最远位置 max_reach max(max_reach, i nums[i]) # 如果到达了当前跳跃的边界 if i current_end: jumps 1 current_end max_reach # 如果已经能到终点 if current_end n - 1: break return jumps # 测试 nums [2, 3, 1, 1, 4] print(f最少需要 {jump(nums)} 次跳跃) # 输出: 2题目6划分字母区间LeetCode 763问题将字符串划分为尽可能多的片段使得同一个字母最多出现在一个片段中。贪心策略记录每个字母最后出现的位置在区间内扩展右边界pythondef partition_labels(s): 划分字母区间 返回每个片段的长度列表 # 记录每个字符最后出现的位置 last_pos {} for i, char in enumerate(s): last_pos[char] i result [] start 0 end 0 for i, char in enumerate(s): # 更新当前片段的结束位置 end max(end, last_pos[char]) # 如果当前位置就是结束位置 if i end: result.append(end - start 1) start end 1 return result # 测试 s ababcbacadefegdehijhklij print(f分区长度: {partition_labels(s)}) # [9, 7, 8]题目7加油站LeetCode 134问题环形路上有 n 个加油站第 i 个加油站有 gas[i] 升汽油从 i 到 i1 需要 cost[i] 升汽油。从哪个加油站出发可以走完全程贪心策略如果总油量 总消耗一定有解从油量赤字之后的下一个位置开始pythondef can_complete_circuit(gas, cost): 加油站问题 返回起点索引如果无法走完返回 -1 total_gas 0 total_cost 0 current_gas 0 start 0 for i in range(len(gas)): total_gas gas[i] total_cost cost[i] current_gas gas[i] - cost[i] # 如果当前油量不够说明从 start 到 i 这段都不行 if current_gas 0: start i 1 current_gas 0 # 如果总油量 总消耗一定有解 return start if total_gas total_cost else -1 # 测试 gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] print(f从第 {can_complete_circuit(gas, cost)} 个加油站出发)三、贪心算法使用建议✅ 什么时候用贪心问题具有贪心选择性质问题的最优解包含子问题的最优解经典问题找零钱、活动选择、哈夫曼编码、最小生成树、最短路径(Dijkstra)❌ 什么时候不用贪心需要回溯才能找到最优解如背包问题的 0-1 版本当前选择会影响未来的选择如旅行商问题贪心能得到局部最优但不能保证全局最优四、常见题型总结类型经典题目贪心策略区间问题活动选择、无重叠区间按右端点排序分配问题分发饼干、分发糖果排序后从最小开始匹配跳跃问题跳跃游戏 I/II维护能到达的最远位置字符串处理划分字母区间、移除数字贪心选择边界数组处理加油站、股票买卖累加差值找转折点五、时间复杂度总结排序类分发饼干、活动选择O(n log n)遍历类跳跃游戏、加油站O(n)空间复杂度通常 O(1) 或 O(n)