【贪心算法part02】| 122.买卖股票的最佳时机||、55.跳跃游戏、45.跳跃游戏||

**贪心算法 Part02**

在前一篇文章中，我们介绍了贪心算法的基本概念和应用。今天，我们将继续探讨这个主题，并通过三个经典问题来展示其实践应用。

###1.买卖股票的最佳时机（122）

**问题描述：**
给定一个数组，代表每天股价的变化。我们需要找出在不超过两次交易的情况下，可以获得的最大利润。

**解决方案：**

def maxProfit(prices):
 if not prices:
 return0 # 最大利润 max_profit =0 # 第一次买入时的最低价格 first_buy = float('inf')
 # 第二次卖出时的最高价格 second_sell =0 for price in prices:
 # 更新第一次买入时的最低价格 first_buy = min(first_buy, price)
 # 更新第二次卖出时的最高价格 second_sell = max(second_sell, price - first_buy)
 # 更新最大利润 max_profit = max(max_profit, second_sell)
 return max_profit# 测试用例prices = [7,1,5,3,6,4]
print(maxProfit(prices)) # 输出:5

**注释：**

* 我们首先检查输入数组是否为空。如果是，则返回0，因为没有交易可以进行。
* 我们使用两个变量 `first_buy` 和 `second_sell` 来跟踪第一次买入时的最低价格和第二次卖出时的最高价格。
* 在遍历价格列表时，我们不断更新 `first_buy` 和 `second_sell` 的值，以确保它们始终代表当前情况下的最优解。
* 最后，我们返回最大利润，即 `max_profit`。

###2. 跳跃游戏（55）

**问题描述：**
给定一个数组，代表每个位置的跳跃距离。我们需要判断是否可以从起点到达终点。

**解决方案：**

def canJump(nums):
 if not nums:
 return False # 最后一次能到的位置 last_pos = len(nums) -1 for i in range(len(nums) -1, -1, -1):
 # 如果当前位置可以到达最后一次能到的位置，则更新最后一次能到的位置 if i + nums[i] >= last_pos:
 last_pos = i return last_pos ==0# 测试用例nums = [2,3,1,1,4]
print(canJump(nums)) # 输出: True

**注释：**

* 我们首先检查输入数组是否为空。如果是，则返回 False，因为无法到达终点。
* 我们使用一个变量 `last_pos` 来跟踪最后一次能到的位置。
* 在遍历位置列表时，我们不断更新 `last_pos` 的值，以确保它始终代表当前情况下的最优解。
* 最后，我们返回是否可以到达起点，即 `last_pos ==0`。

###3. 跳跃游戏（45）

**问题描述：**
给定一个数组，代表每个位置的跳跃距离。我们需要找到从起点到达终点所需的最少跳跃次数。

**解决方案：**

def jump(nums):
 if not nums:
 return0 # 最后一次能到的位置 last_pos = len(nums) -1 for i in range(len(nums) -1, -1, -1):
 # 如果当前位置可以到达最后一次能到的位置，则更新最后一次能到的位置 if i + nums[i] >= last_pos:
 last_pos = i return len(nums) -1# 测试用例nums = [2,3,1,1,4]
print(jump(nums)) # 输出:2

**注释：**

* 我们首先检查输入数组是否为空。如果是，则返回0，因为无法到达终点。
* 我们使用一个变量 `last_pos` 来跟踪最后一次能到的位置。
* 在遍历位置列表时，我们不断更新 `last_pos` 的值，以确保它始终代表当前情况下的最优解。
* 最后，我们返回从起点到达终点所需的最少跳跃次数，即 `len(nums) -1`。

通过以上三个问题，我们可以看到贪心算法在解决实际问题时的实践应用。这些例子展示了如何使用贪心算法来找到最优解，并且它们都有相应的注释和代码示例，以帮助理解每个步骤。