LeetCode热题100之贪心算法
1.买卖股票的最佳时机
思路分析：即需要找出某一天的最低价格和它后面几天的最高价格差。
- 维护一个变量min_price，表示到目前为止遇到的最低股票价格；
- 遍历prices数组，在每一天的价格上：
- 更新min_price为当前的价格和min_price中的较小值；
- 计算当天价格减去min_price的利润，即当天卖出的最大可能利润；
- 将这个利润与之前记录的max_profit做比较，保留较大的利润
- 最终得到的max_profit就是最大利润
具体实现代码（详解版）：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min_price = INT_MAX; // 初始化为一个很大的数
int max_profit = 0; // 初始最大利润为0
for (int price : prices) {
// 更新最小价格
min_price = min(min_price, price);
// 计算当前价格与最小价格的差值，并更新最大利润
max_profit = max(max_profit, price - min_price);
}
return max_profit;
}
};
- 时间复杂度为O(n).
2.跳跃游戏
思路分析：贪心法适用于这种问题，因为我们每一步只需要关注从当前的最远位置能否再往前推进。只要每次都记录并更新最远位置，就能知道是否能够到达最后一个位置。
- 定义最远可达位置：在遍历数组时，记录当前可以到达的最远位置。定义一个变量 farthest 来表示从起点到当前位置可以到达的最远下标。；
- 遍历数组：
- 如果在遍历到某个位置 i 时，发现 farthest 小于 i，说明从起点出发无法到达位置 i，因此直接返回 false。
- 从第一个位置开始遍历，每次更新 farthest 为当前位置 i 加上 nums[i]，即 farthest = max(farthest, i + nums[i])。
- 判断是否能到达最后一个位置
- 在遍历结束后，如果 farthest 已经超过或等于最后一个下标，说明可以到达最后一个位置，返回 true。
- 否则返回 false。
具体实现代码（详解版）：
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int farthest = 0;//可以跳跃到的最远位置
for(int i = 0 ; i < n ; i ++){
if(farthest < i){//从起点无法到达i
return false;
}
farthest = max(farthest,i + nums[i]);//更新farthest
}
return farthest >= n - 1 ? true : false; //最后的判断
}
};
- 时间复杂度：O(n);
- 空间复杂度：O(n)
3.跳跃游戏II
思路分析：这是一个最小跳跃次数的问题，可以使用贪心算法来解决
- 定义变量：
- 用min_jump记录总的跳跃数；
- 用current_end记录当前跳跃的边界，即在这一条内能跳到的最远位置
- 用farthest记录可以到达的最远位置
- 遍历数组
- 遍历数组，逐步更新farthest表示当前位置能到达的最远位置；
- 当遍历到边界current_end时，说明必须进行一次跳跃来继续前进，此时min_jump增1，并更新current_end为farthest
- 结束条件：如果currnt_end已经到达或超过数组末尾，说明可以到达终点，返回min_jump即可。
具体实现代码（详解版）：
class Solution {
public:
int jump(vector<int>& nums) {
int min_jump = 0;// 记录跳跃次数
int farthest = 0;// 当前跳跃的边界
int current_end = 0;// 在当前跳跃中能够到达的最远位置
int n = nums.size();
if(n <= 1) return 0;//如果数组长度为或更小，不需要跳跃
for(int i = 0 ; i < n ; i ++){
farthest = max(farthest,i + nums[i]);//更新最远位置
//到达当前跳跃的边界，必须进行一次跳跃
if(i == current_end){
min_jump ++;//次数加1
current_end = farthest;//更新跳跃边界为最远位置
// 如果已经可以到达或超过最后一个位置，直接返回跳跃次数
if(farthest >= n -1) break;
}
}
return min_jump;
}
};
- 时间复杂度：O(n）
- 空间复杂度：O(1)
4.划分字母区间
思路分析：这个问题要求将字符串 s 划分为尽可能多的片段，并确保每个片段内的字符不会重复出现。我们可以通过 贪心算法 来实现这个需求
- 记录每个字符的最后出现位置：首先，我们需要确定每个字符在字符串中最后出现的位置。因为一旦一个字符在某个位置被包含在某个片段中，我们就可以保证该字符在这个片段的范围内，后续再出现该字符时就不能被包含到当前片段中，而必须开始新的片段。
- 我们遍历字符串 s，利用一个哈希表 lastIndex 记录每个字符在字符串中的最后位置。这样可以随时查询到某个字符的最后出现位置。
为什么记录最后出现位置：
例如，在字符串 “abac” 中，字符 ‘a’ 在索引 0 和索引 3 出现，我们需要知道 ‘a’ 在索引 3 处最后一次出现，这样我们就可以在第 0 到第 3 索引之间创建一个片段，确保 ‘a’ 被包含在这个片段内。
- 确定片段的范围：在遍历字符串时，我们使用一个变量 end 来记录当前片段的结束位置。这个结束位置会随着我们遇到字符并更新字符的最后出现位置而动态变化。
- 当遍历到一个字符 s[i] 时，我们查找该字符的 最后出现位置，并更新 end 为 max(end, lastIndex[s[i]])，确保 end 记录了当前片段的最远边界。
- 如果当前的索引 i 达到了 end，说明当前片段已经完成，因为所有在这个片段内的字符的最后出现位置都已经在片段内了。
- 划分片段并记录片段长度：当我们确定一个片段已经结束时，我们就记录该片段的长度，并且将 start 更新为下一个片段的起始位置。这样就能不断划分新的片段。
- 当 i == end 时，说明当前片段已经完全确定，片段的长度是 end - start + 1；
- 记录片段长度后，将 start 更新为 i + 1，开始下一个片段的划分。
具体实现代码（详解版）；
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> result; // 用来保存最终的片段长度
unordered_map<char, int> lastIndex; // 用于记录每个字符最后出现的位置
// Step 1: 记录每个字符的最后出现位置
for (int i = 0; i < s.size(); i++) {
lastIndex[s[i]] = i;
}
int start = 0, end = 0; // start记录当前片段的起始位置，end记录当前片段的结束位置
// Step 2: 遍历字符串确定片段
for (int i = 0; i < s.size(); i++) {
end = max(end, lastIndex[s[i]]); // 更新当前片段的结束位置
if (i == end) { // 当前片段结束
result.push_back(end - start + 1); // 记录当前片段的长度
start = i + 1; // 更新下一个片段的起始位置
}
}
return result; // 返回所有片段的长度
}
};
- 时间复杂度：O(1)
- 空间复杂度：O(1).