免费入驻的外贸网站,校园生活网页设计图片模板,wordpress七牛插件,wordpress 自定义目录目录
1 121. 买卖股票的最佳时机
2 55. 跳跃游戏
3 45. 跳跃游戏 II
4 763. 划分字母区间 菜鸟做题#xff0c;语言是 C 1 121. 买卖股票的最佳时机
解题思路#xff1a;
维护一个变量 max_pricemax_price 用于存储排在 i 天之后的股票最高价格第 i 天的最高利润 …目录
1 121. 买卖股票的最佳时机
2 55. 跳跃游戏
3 45. 跳跃游戏 II
4 763. 划分字母区间 菜鸟做题语言是 C 1 121. 买卖股票的最佳时机
解题思路
维护一个变量 max_pricemax_price 用于存储排在 i 天之后的股票最高价格第 i 天的最高利润 max_price - 第 i 天的股票价格
思路说明
假设股票价格数组为 [715364]从后往前遍历数组以计算 max_price如下图所示。 1如果第 i 天的股票价格低于 max_price则
第 i 天的最高利润 max_price - 第 i 天的股票价格需要更新 profit不需要更新 max_price
2如果第 i 天的股票价格高于 max_price则
第 i 天的最高利润 0不需要更新 profit需要更新 max_price 在如下代码中我用的是变量 ans 代表 profit 的含义。 class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int ans 0, max_price 0;for (int i n - 1; i 0; --i) {if (prices[i] max_price) {max_price prices[i];} else {ans max(ans, max_price - prices[i]);}}return ans;}
}; 2 55. 跳跃游戏
解题思路
遍历 nums 数组不断更新最远距离 maxDistance如果 maxDistance nums.size() - 1则返回 true
思路说明图 遍历第 0 个元素maxDistance 2遍历第 1 个元素maxDistance 1 3 4遍历第 2 个元素maxDistance 4 2 1以此类推
class Solution {
public:bool canJump(vectorint nums) {int maxDistance 0;for (int i 0; i nums.size(); i) {if (i maxDistance) {maxDistance max(i nums[i], maxDistance);}}return maxDistance nums.size() - 1;}
}; 3 45. 跳跃游戏 II
解题思路
仍然是遍历 nums 数组每次更新 maxDistance 范围针对在同一次更新后被包含进去的位置算作一次跳跃
思路说明图 将 maxDistance 初始化为 0被包含进去的 0 号位置属于第一次跳跃count 0。根据 0 号位置更新 maxDistance 为 2被包含进去的 1、2 号位置属于第二次跳跃count 1。根据 1、2 号位置更新 maxDistance 为 4被包含进去的 3、4 号位置属于第三次跳跃count 2。 如果更新 maxDistance 后发现 maxDistance nums.size() - 1则返回 count 1 即可。为什么是 count 1因为目前只是能够跳跃到达 nums.size() - 1但还没有跳。 class Solution {
public:int jump(vectorint nums) {int maxDistance 0;int pos 0, count 0;if (pos nums.size() - 1)return 0;while (pos nums.size()) {int temp maxDistance;while (pos temp) {maxDistance max(maxDistance, pos nums[pos]);if (maxDistance nums.size() - 1) {return count 1;}pos;}count;}return count;}
}; 4 763. 划分字母区间
解题思路
遍历字符串 s记录每个字母的最后出现位置设置 begin 0即从 0 号字母开始划分字符串根据每个字母的最后出现位置不断更新 end若当前位置 end则 begin ~ end 之间是一个子串
思路说明图
图中的 B 代表 begin即子串的开头E 代表 end即子串的结尾初始化 begin 为 0初始化 E 为第一个字母的最后出现位置
我们需要保证的是 B 和 E 之间的所有字母不能横跨两个子串。换句话说B 和 E 之间的 b 和 c 的最后出现位置不能超过 a 的最后出现位置 E 。如果超过了我们需要更新 E 。 第一轮首先访问 a并且设置 E 为 a 的最后出现位置接着访问 b由于 b 的最后出现位置没有超过 E因此不需要更新 E。以此类推访问到 c由于 c 的最后出现位置没有超过 E因此不需要更新 E 。最后指针 i 移动到 E说明 B 和 E 之间的字母只会出现在该区间内由此得到第一个子串。
第二轮B 更新到 E 的后面一个位置模仿第一轮的操作继续访问。 由于篇幅有限因此图中省略了一些步骤请自行脑补。 class Solution {
public:vectorint partitionLabels(string s) {unordered_mapchar, int charEnd;for (int i 0; i s.size(); i) {charEnd[s[i]] i;}vectorint ans;int begin 0, end 0;for (int i 0; i s.size(); i) {end max(end, charEnd[s[i]]);if (i end) {ans.push_back(end - begin 1);begin end 1;}}return ans;}
}; 上述代码用的是哈希表 charEnd 来存储字母的最后出现位置换成 vectorint 也行。 这样做会超出内存限制
int subStrEnd charEnd[s[0]];
while (begin s.size()) {while (end subStrEnd) {subStrEnd max(subStrEnd, charEnd[s[end]]);end;}ans.push_back(end - begin);begin end;
}
