【LeetCode 热题 100】买卖股票的最佳时机 / 跳跃游戏 / 划分字母区间

⭐️个人主页：@小羊 ⭐️所属专栏：LeetCode 热题 100 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

买卖股票的最佳时机

• 买卖股票的最佳时机

class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0, m = 1e4 + 1;for (auto e : prices){m = min(m, e);res = max(res, e - m);}   return res;}
};

---

跳跃游戏

• 跳跃游戏

贪心策略：类似层序遍历，每层都尽可能走到最远。

class Solution {
public:bool canJump(vector<int>& nums) {int left = 0, right = 0, maxpos = 0, n = nums.size();while (left <= right){if (maxpos >= n - 1) return true;for (int i = left; i <= right; i++){maxpos = max(maxpos, nums[i] + i);}left = right + 1;right = maxpos;}return false;}
};

---

跳跃游戏 II

• 跳跃游戏 II

动态规划解法：dp[i] 表示走到i位置的最小跳跃数。
则 dp[i] 可由 [0, i - 1] 区间中某个位置跳跃一步能超过当前位置的值转换而来。

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

贪心解法：类似跳跃游戏I

class Solution {
public:int jump(vector<int>& nums) {int left = 0, right = 0, maxpos = 0, n = nums.size(), res = 0;while (true){if (maxpos >= n - 1) return res;for (int i = left; i <= right; i++){maxpos = max(maxpos, nums[i] + i);}left = right + 1;right = maxpos;res++;}}
};

---

划分字母区间

• 划分字母区间

• 预处理字符最后出现位置：
  遍历字符串，记录每个字符最后一次出现的索引位置。例如，last[‘a’-‘a’] 存储字符 ‘a’ 在字符串中最后一次出现的位置。
• 贪心策略划分区间：
  维护两个指针 begin 和 end，表示当前分区的起始和结束位置。
  遍历字符串，对于每个字符，更新 end 为当前字符最后出现位置和 end 的较大值。
  当遍历到 end 位置时，说明当前分区内的所有字符不会出现在后续分区中，此时记录分区长度并更新 begin 为下一个分区的起始位置。

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

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~