贪心算法
贪心算法（Greedy Algorithm）是一种在每一步都选择当前最优解的策略，希望通过局部最优解达到全局最优解。虽然贪心算法不一定能得到全局最优解，但在许多问题中它能够高效地得到近似最优解或最优解。
贪心算法基础
贪心算法的特点
- 贪心选择性质：每一步都选择当前最优的选择
- 最优子结构：问题的最优解包含子问题的最优解
- 无后效性：当前的选择不会影响未来的选择
贪心 vs 动态规划
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择方式 | 局部最优 | 考虑所有可能 |
| 子问题 | 只解决一次 | 可能重复解决 |
| 时间复杂度 | 通常较低 | 通常较高 |
| 正确性 | 需要证明 | 总是正确 |
经典贪心问题
1. 活动选择问题
题目：选择最多的互不重叠的活动。
def activity_selection(start, finish):
activities = list(zip(start, finish))
activities.sort(key=lambda x: x[1]) # 按结束时间排序
selected = [0]
last_finish = activities[0][1]
for i in range(1, len(activities)):
if activities[i][0] >= last_finish:
selected.append(i)
last_finish = activities[i][1]
return selected
2. 区间调度问题
题目：移除最少的区间，使得剩余区间互不重叠。
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # 按结束时间排序
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end:
count += 1
else:
end = intervals[i][1]
return count
3. 跳跃游戏
题目：判断能否到达最后一个位置。
def can_jump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True
4. 跳跃游戏 II
题目：最少跳跃次数到达最后一个位置。
def jump(nums):
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
if current_end >= len(nums) - 1:
break
return jumps
5. 分发糖果
题目：每个孩子至少一个糖果，相邻孩子中评分高的孩子获得更多糖果。
def candy(ratings):
n = len(ratings)
candies = [1] * n
# 从左到右
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
6. 无重叠区间
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end:
count += 1
else:
end = intervals[i][1]
return count
7. 用最少数量的箭引爆气球
def find_min_arrow_shots(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for start, finish in points[1:]:
if start > end:
arrows += 1
end = finish
return arrows
8. 买卖股票的最佳时机
题目：只能进行一次交易，求最大利润。
def max_profit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
max_profit = max(max_profit, price - min_price)
min_price = min(min_price, price)
return max_profit
9. 买卖股票的最佳时机 II
题目：可以进行多次交易，求最大利润。
def max_profit_multiple(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
10. 加油站
题目：找到可以绕一圈的起始加油站。
def can_complete_circuit(gas, cost):
total_gas = sum(gas)
total_cost = sum(cost)
if total_gas < total_cost:
return -1
start = 0
tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start
贪心算法的证明
1. 交换论证
证明：如果存在一个最优解，我们可以通过交换将其转换为贪心解，且不会使解变差。
2. 数学归纳法
证明：对于所有规模的问题，贪心选择都是最优的。
3. 反证法
假设贪心解不是最优解，然后推导出矛盾。
常见题目
1. 划分字母区间
def partition_labels(s):
last_occurrence = {char: i for i, char in enumerate(s)}
result = []
start = 0
end = 0
for i, char in enumerate(s):
end = max(end, last_occurrence[char])
if i == end:
result.append(end - start + 1)
start = i + 1
return result
2. 任务调度器
def least_interval(tasks, n):
from collections import Counter
counts = Counter(tasks)
max_count = max(counts.values())
num_max = sum(1 for count in counts.values() if count == max_count)
return max(len(tasks), (max_count - 1) * (n + 1) + num_max)
3. 重构字符串
def reorganize_string(s):
from collections import Counter
import heapq
counts = Counter(s)
heap = [(-count, char) for char, count in counts.items()]
heapq.heapify(heap)
result = []
prev_count, prev_char = 0, ''
while heap:
count, char = heapq.heappop(heap)
result.append(char)
if prev_count < 0:
heapq.heappush(heap, (prev_count, prev_char))
prev_count, prev_char = count + 1, char
if len(result) != len(s):
return ""
return ''.join(result)
总结
贪心算法是解决最优化问题的重要方法：
- 核心思想：每一步选择当前最优解
- 适用条件：贪心选择性质 + 最优子结构
- 常见问题：区间调度、跳跃游戏、股票买卖、任务调度
- 证明方法：交换论证、数学归纳法、反证法
掌握贪心算法能够帮助你高效解决许多优化问题，但需要注意证明其正确性。
算法部分的学习就到这里了！接下来，让我们学习面向对象设计，这是面试中的重要环节。