力扣hot100——贪心

77.买股票的最佳时机

题目描述

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

思路一：贪心

贪心策略：我们要得到最大利润，最好就是价格最低买入，价格最高卖出。具体的方法是在遍历prices数组时维护价格的最小值Min,当访问到prices[i]，假设此时卖出，那么所能得到的最大利润为prices[i]-Min，对于i=0~pricesNums,取最大值。

代码一

int maxProfit(int* prices, int pricesSize) {int Min = prices[0];  // 初始化最低股价为第一天价格int ans = 0;          // 初始化最大利润为0for (int i = 1; i < pricesSize; i++) {  // 从第二天开始遍历// 计算当前卖出能获得的利润，并与历史最大值比较ans = fmax(prices[i] - Min, ans);   // 更新最低股价，确保Min始终是已遍历天数中的最小值Min = fmin(prices[i], Min);         }return ans;  // 返回最大利润
}

思路二：dp

1.定义状态

• dp[i][0]：表示第 i 天 持有股票 时的最大现金。
• dp[i][1]：表示第 i 天 不持有股票 时的最大现金。

2.初始化

• dp[0][0] = -prices[0]：第 0 天持有股票，现金为负的股票价格（表示买入股票）。
• dp[0][1] = 0：第 0 天不持有股票，现金为 0。

3.状态转移方程

• 持有股票：

  • 如果第 i 天持有股票，可能是前一天已经持有股票，或者第 i 天买入股票，即前i-1天买入或者第i天买入两种情况。

  $$dp[i][0]=max(dp[i-1][0],-prices[i])$$

• 不持有股票：

  • 如果第 i 天不持有股票，可能是前一天已经不持有股票，或者第 i 天卖出股票，即前i-1天卖出或者第i天才卖出两种情况。

  $$dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])$$

4.最终结果

• 最终结果为 dp[pricesSize-1][1]，即最后一天不持有股票时的最大现金,因为不持有股票手中的现金肯定更大。

代码二

#include <stdio.h>
#include <limits.h> // 用于 INT_MINint maxProfit(int* prices, int pricesSize) {if (pricesSize == 0) return 0; // 空数组直接返回0// 定义动态规划数组int dp[pricesSize][2];// 初始化dp[0][0] = -prices[0]; // 第0天持有股票dp[0][1] = 0;          // 第0天不持有股票// 动态规划递推for (int i = 1; i < pricesSize; i++) {// 第i天持有股票：前一天已经持有，或者第i天买入dp[i][0] = fmax(dp[i - 1][0], -prices[i]);// 第i天不持有股票：前一天已经不持有，或者第i天卖出dp[i][1] = fmax(dp[i - 1][1], dp[i - 1][0] + prices[i]);}// 返回最后一天不持有股票的最大现金return dp[pricesSize - 1][1];
}

78.跳跃游戏

题目描述

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

思路：贪心

1. 贪心算法：贪心策略，通过维护一个变量 sum 来记录当前能到达的最远位置。
   • 在遍历数组时，不断更新 sum，确保它始终表示从当前位置能跳到的最远位置。
2. 初始化：
   • 将 sum 初始化为 0，表示初始位置。
3. 遍历数组：
   • 对于每个位置 i，检查是否能从之前的位置跳到当前位置（即 sum >= i）。
   • 如果能跳到当前位置，则更新 sum 为 max(sum, i + nums[i])，表示从当前位置能跳到的最远位置。
   • 如果 sum 已经超过或等于最后一个位置（numsSize - 1），则返回 true。

代码

bool canJump(int* nums, int numsSize) {int sum = 0;for (int i = 0; i < numsSize; i++) {// 如果当前位置无法到达，直接返回 falseif (sum < i) {return false;}// 更新能到达的最远位置sum = fmax(sum, i + nums[i]);// 如果最远位置已经超过或等于最后一个位置，返回 trueif (sum >= numsSize - 1) {return true;}}return false;
}

79.跳跃游戏Ⅱ

题目描述

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

思路一：贪心

• 使用贪心策略，每次在当前跳跃范围内选择能跳得最远的位置。
• 维护两个变量：
  • sum：当前能够到达的最远位置。
  • cur：在当前跳跃范围内，能够到达的最远位置。
• 当遍历到 sum 时，表示当前跳跃范围已经用尽，需要进行一次新的跳跃，并更新 sum 为 cur。

代码一

int jump(int* nums, int numsSize) {if (numsSize <= 1) return 0; // 如果数组长度为 0 或 1，不需要跳跃int sum = 0; // 当前能够到达的最远位置int cnt = 0; // 跳跃次数int cur = 0; // 在当前跳跃范围内，能够到达的最远位置for (int i = 0; i < numsSize - 1; i++) {if (sum >= numsSize - 1) return cnt; // 如果已经能够到达终点，直接返回跳跃次数// 更新当前能够到达的最远位置if (cur < nums[i] + i) {cur = nums[i] + i;}// 当遍历到 sum 时，表示当前跳跃范围已经用尽，需要进行一次新的跳跃if (sum == i) {sum = cur; // 更新 sum 为当前能够到达的最远位置cnt++;     // 增加跳跃次数}}return cnt; // 返回跳跃次数
}

思路二：动态规划

1. 定义状态：

   • 设 dp[i] 表示从起点（位置 0）跳到位置 i 所需的最小跳跃次数。

2. 状态转移方程：

   • 对于每个位置 i，遍历所有可以跳到 i 的位置 j（即 j + nums[j] >= i），然后更新 dp[i] 为 dp[j] + 1 的最小值。

   • 状态转移方程可以表示为：

     dp[i]=min⁡(dp[i],dp[j]+1)其中j+nums[j]≥i

3. 初始化：

   • dp[0] = 0，因为起点不需要跳跃。
   • 其他位置的 dp[i] 初始化为一个较大的值（如 INT_MAX），表示暂时无法到达。

4. 最终结果：

   • dp[numsSize - 1] 即为从起点跳到终点的最小跳跃次数。

代码二

#include <limits.h>int jump(int* nums, int numsSize) {if (numsSize <= 1) return 0; // 如果数组长度为 0 或 1，不需要跳跃int dp[numsSize]; // 定义 dp 数组for (int i = 0; i < numsSize; i++) {dp[i] = INT_MAX; // 初始化 dp 数组为最大值}dp[0] = 0; // 起点不需要跳跃// 动态规划求解for (int i = 1; i < numsSize; i++) {for (int j = 0; j < i; j++) {if (j + nums[j] >= i) { // 如果可以从 j 跳到 idp[i] = fmin( dp[i] ,dp[j] + 1); // 更新 dp[i]}}}return dp[numsSize - 1]; // 返回到达终点的最小跳跃次数
}

80.划分字母区间

题目描述

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

思路：贪心

1. 问题描述：
   • 给定一个字符串 s，要求将字符串划分为若干片段，使得每个字母最多出现在一个片段中。
   • 返回每个片段的长度。
2. 关键点：
   • 每个字母的最后出现位置决定了片段的边界。
   • 遍历字符串时，动态更新当前片段的结束位置。
3. 算法步骤：
   • 首先记录每个字母的最后出现位置。
   • 遍历字符串，更新当前片段的结束位置。
   • 当遍历到当前片段的结束位置时，记录片段长度，并开始下一个片段。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int* partitionLabels(char* s, int* returnSize) {// 分配结果数组的内存int* ans = malloc(sizeof(int) * 500);// 初始化返回的片段数量为 0*returnSize = 0;// 字符串的长度int n = strlen(s);// 记录每个字母的最后出现位置int last[26] = {0};// 遍历字符串，记录每个字母的最后出现位置for (int i = 0; i < n; i++) {last[s[i] - 'a'] = i;}// 初始化当前片段的起始位置和结束位置int start = 0, end = 0;// 遍历字符串for (int i = 0; i < n; i++) {// 更新当前片段的结束位置end = fmax(end, last[s[i] - 'a']);// 如果遍历到当前片段的结束位置if (i == end) {// 记录当前片段的长度ans[(*returnSize)++] = end - start + 1;// 更新下一个片段的起始位置start = end + 1;}}// 返回结果数组return ans;
}