LeetCode刷题记录（贪心算法篇）
LeetCode刷题记录（贪心算法篇），个人向。
[121] Best Time to Buy and Sell Stock
难度：Easy
语言：C++
题目描述。
遍历一遍数组即可。其中记录一下历史价格最低值，然后查看当前价格减去历史最低值（即当前利润）是否大于最大利润即可，最后返回最大利润。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int max_profit = 0;
int buy = prices[0];
for (int p : prices) {
if (p <= buy) {
buy = p;
} else if (p - buy > max_profit) {
max_profit = p - buy;
}
}
return max_profit;
}
};
[55] Jump Game
难度：Medium
语言：C++
题目描述。
这道题只要想清楚，我们不需要关心怎么从起点跳到终点，只需要知道能不能跳到终点，这道题就变得很简单。
我们可以在遍历数组的同时更新能跳到的位置的覆盖范围（覆盖到了，就说明能跳到这里，怎么跳的不关心），最后看覆盖的范围有没有到最后一个位置即可。
class Solution {
public:
bool canJump(vector<int> &nums) {
int curPos = 0;
int maxJump = 0;
int dest = nums.size() - 1;
while (maxJump < dest && curPos <= maxJump) {
maxJump = max(maxJump, curPos + nums[curPos]);
curPos += 1;
}
return maxJump >= dest;
}
};
[45] Jump Game II
难度：Medium
语言：C++
题目描述。
相比上一题，这题需要记录步数。
我们依然不用关注是如何跳到终点的，即不需要关注具体路径。
相比上一题，我们需要分别记录一下当前step能到达的最远距离curMaxPos和下一step能到达的最远距离nextMaxPos，然后在curPos到达curMaxPos时说明当前step已经走完，nextMaxPos已经更新完毕，此时更新一下step和curMaxPos，开始下一轮迭代。
注意for循环判断条件为curMaxPos < dest而不是nextMaxPos < dest，否则最终step可能会少一。
class Solution {
public:
int jump(vector<int> &nums) {
int step = 0;
int curMaxPos = 0;
int nextMaxPos = 0;
int dest = nums.size() - 1;
for (int curPos = 0; curMaxPos < dest; ++curPos) {
nextMaxPos = max(nextMaxPos, curPos + nums[curPos]);
if (curPos == curMaxPos) {
step += 1;
curMaxPos = nextMaxPos;
}
}
return step;
}
};
[763] Partition Labels
难度：Medium
语言：C++
题目描述。
和贪心好像没多大关系。
先遍历一遍字符串，统计各个字符的最远出现位置。
然后，第二次遍历字符串，遍历同时记录一下遍历到的字符的最远出现下标（end = max(end, map[s[i] - 'a']);）。当遍历到达记录的遍历过字符的最远出现下标了，就说明当前片段遍历结束，记录一下结果（end - start + 1），然后开始下一片段（start = end + 1;）。
class Solution {
public:
vector<int> partitionLabels(string s) {
int length = s.size();
int map[26] = {0};
int start = 0, end = 0;
vector<int> result;
for (int i = 0; i < length; ++i) {
map[s[i] - 'a'] = i;
}
for (int i = 0; i < length; ++i) {
end = max(end, map[s[i] - 'a']);
if (i == end) {
result.push_back(end - start + 1);
start = end + 1;
}
}
return result;
}
};
总结
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。