122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
局部最优：在价格趋势呈上涨的两端买入和卖出，保证利润为正值；比如：Day2买入，Day3卖出；
全局最优：计算所有局部最优的和，求得最大利润
class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0;for (int i = 0; i < prices.size() - 1; i++) {int diff = prices[i + 1] - prices[i];if (diff > 0) {res += diff;}}return res;}
};
55. 跳跃游戏
55. 跳跃游戏
| i | nums[i] | i+nums[i] | mx最远能到达的位置 | 备注 |
|---|---|---|---|---|
| 0 | 2 | 2 | 2 | |
| 1 | 3 | 3 | 4 | 可以到达最后一个位置 |
| 2 | 1 | 3 | 4 | |
| 3 | 1 | 4 | 4 | |
| 4 | 4 | 8 | 8 |
| i | nums[i] | i+nums[i] | mx最远能到达的位置 | 备注 |
|---|---|---|---|---|
| 0 | 3 | 3 | 3 | |
| 1 | 2 | 3 | 3 | |
| 2 | 1 | 3 | 3 | |
| 3 | 0 | 3 | 3 | 最远可以到达此位置 |
| 4 | 4 | - | - | 不能跳到此位置 |
局部最优：最远能跳到的位置，
全局最优：最后更新的最远可以跳到的位置是否可以到达数组的最后一个下标
class Solution {
public:bool canJump(vector<int>& nums) {int mx = 0; // 最远能跳到的位置// if (nums.size() == 1) {// // 数组只有一个元素，即我们跳跃的起点，肯定可以到到达// return true;// }for (int i = 0; i <= mx; ++i) { // 在最远位置范围内的可以继续跳跃mx = max(mx, i + nums[i]); // 更新最远可以到达的位置if (mx >= nums.size() - 1) { // 最远位置可以覆盖数组最后一个下标return true;}}return false;}
};
45. 跳跃游戏II
45. 跳跃游戏II
| i | nums[i] | i+nums[i] | maxPos最远能到达的位置 | 备注 |
|---|---|---|---|---|
| 0 | 2 | 2 | 2 | |
| 1 | 2 | 3 | 3 | 第一步跳跃可覆盖的范围，可以在此处进行第二步跳跃 |
| 2 | 3 | 5 | 5 | 第二步跳跃可以达到的最远的位置；同时可以到达最后一个位置，共跳跃2步，0->2->5 |
| 3 | 1 | 4 | 5 | |
| 4 | 1 | 5 | 5 | |
| 5 | 0 | 8 | 8 |
局部最优：以 最小步数 增加最远能跳到的位置；每跳跃一步，在前一步跳跃覆盖的范围内寻找下一个可以跳到更远位置的下标，作为该步跳跃的起始位置；
例如：nums = [2,2,3,1,1,0]; 起始位置nums[0] = 2; 可以跳到下标为1， 和下标为2的两个位置；从这两个位置中选取可以跳的更远的一个下标作为新的其实位置；i = 1时maxPos = max(2, 1 + nums[1]) =3 ；i = 2时maxPos = max(2, 2 + nums[2]) =5 ；所以下标2 作为新的起跳位置。
全局最优：到达数组最后一个下标位置的最小跳跃次数
class Solution {
public:int jump(vector<int>& nums) {int maxPos = 0;int end = 0;int steps = 0;if (nums.size() == 1) {return 0;}for (int i = 0; i < nums.size() - 1; ++i) {maxPos = max(maxPos, i + nums[i]);if (i == end) { // 遇到边界，更新边界，并且步数加 1end = maxPos;steps++;}}return steps;}
};
1005 K 次取反后最大化的数组和
1005 K 次取反后最大化的数组和
局部最优：较大的正数越多和越大，优先将绝对值大的负数取反；如果负数全部取反后，K次还大于0，将最小的非负数反复取反；
全局最优：数组和达到最大
class Solution {
public:static bool cmp(int a, int b) {return abs(a) > abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp); // 按绝对值由大到小排序for (int i = 0; i < nums.size(); i++) { // 将尽可能多的绝对值大的负数取反if (nums[i] < 0 && k > 0) {nums[i] *= -1;k--;}}// 如果k还大于0，数组已全为非负数，那么反复取反数值最小的元素，将K用完if (k % 2 == 1) nums[nums.size() - 1] *= -1; int sum = 0;for (int nums : nums) { // 求和sum += nums; }return sum;}
};
