买卖股票的最佳时机
Problem
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked
Solution
从左往右遍历记录当前最小值，当日卖出可获得的最大利润为当前值减去前面的最小值。可获得最大利润为这个过程中的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int min_prices = prices[0];
for (int i = 1; i < prices.size(); i ++)
{
ans = max(ans, prices[i] - min_prices);
min_prices = min(min_prices, prices[i]);
}
return ans;
}
};
|
跳跃游戏
Problem
https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-100-liked
Solution
每次跳都选择下一跳尽可能远的跳跃方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool canJump(vector<int>& nums) {
int max_end = 0;
for (int i = 0; i < nums.size()-1 && max_end >= i; i ++)
{
max_end = max(max_end, i + nums[i]);
}
return max_end >= nums.size()-1;
}
};
|
跳跃游戏II
Problem
https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-100-liked
Solution
每次跳都选择尽可能远的跳跃方式，每次到达上一跳可达最远位置时，说明上一跳的最优落脚点已经确定，跳跃次数++。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int max_end = 0;
int n = nums.size();
int jump_pos = 0;
for (int i = 0; i < n-1; i ++)
{
max_end = max(max_end, i + nums[i]);
if (i == jump_pos)
{
ans ++;
jump_pos = max_end;
}
}
return ans;
}
};
|
划分字母区间
Problem
https://leetcode.cn/problems/partition-labels/?envType=study-plan-v2&envId=top-100-liked
Solution
先遍历字符串，找到每个字符最后出现的位置，然后遍历字符串维护该区间出现过的字母的最远位置，直到到达最远位置，代表这是一个合法的最小区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> end_pos(26, -1);
for (int i = 0; i < s.size(); i ++)
{
end_pos[s[i]-'a'] = i;
}
int max_end = 0;
vector<int> ans;
int count = 0;
for (int i = 0; i < s.size(); i ++)
{
max_end = max(max_end, end_pos[s[i]-'a']);
count ++;
if (i == max_end)
{
ans.emplace_back(count);
count = 0;
}
}
return ans;
}
};
|