LeetCode_Hot_100_0">LeetCode Hot 100：贪心算法

121. 买卖股票的最佳时机

class Solution {
public:int maxProfit(vector<int>& prices) {int minPrice = INT_MAX;int maxProfit = 0;for (int& price : prices) {minPrice = min(minPrice, price);maxProfit = max(maxProfit, price - minPrice);}return maxProfit;}
};

思路 1：动态规划

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();// dp[n] 表示从下标范围 [0,i] 中的任意下标出发可以到达的最大下标vector<int> dp(n);// 初始化dp[0] = nums[0];// 状态转移for (int i = 1; i < n; i++) {if (dp[i - 1] < i)return false;dp[i] = max(dp[i - 1], i + nums[i]);}return dp[n - 1] >= n - 1;}
};

思路 2：贪心

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int max_far = 0; // 目前能跳到的最远位置for (int i = 0; i < n; i++) {if (i <= max_far) {max_far = max(max_far, i + nums[i]);if (max_far >= n - 1)return true;}}return false;}
};

45. 跳跃游戏 II

思路 1：贪心

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int pos = n - 1, step = 0;while (pos > 0) {for (int i = 0; i < pos; i++)if (i + nums[i] >= pos) {pos = i;step++;break;}}return step;}
};

思路 2：动态规划

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();// dp[i] 表示到达 i 的最少跳数vector<int> dp(n, INT_MAX);// 初始化dp[0] = 0;// 状态转移for (int i = 1, last = 0; i < n; i++) {while (last < n && last + nums[last] < i)last++;dp[i] = min(dp[i], dp[last] + 1);}return dp[n - 1];}
};

763. 划分字母区间

class Solution {
public:vector<int> partitionLabels(string s) {int n = s.length();vector<int> last(26, 0);for (int i = 0; i < n; i++)last[s[i] - 'a'] = i;vector<int> ans;int start = 0, end = 0;for (int i = 0; i < n; i++) {end = max(end, last[s[i] - 'a']);if (i == end) {ans.push_back(end - start + 1);start = end + 1;}}return ans;}
};