day28 貪心2
122.買賣股票的最佳時(shí)機(jī)II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
int buyPrice = prices[0];
for (int i = 1; i < prices.size(); i ++) {
if (prices[i] > buyPrice) {
res += prices[i] - buyPrice;
}
buyPrice = prices[i];
}
return res;
}
};
55. 跳躍游戲
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxSteps = nums[0];
for (int i = 1; i < nums.size(); i ++) {
if (maxSteps < i) {
return false;
}
maxSteps = max(maxSteps, i + nums[i]);
}
return true;
}
};
45.跳躍游戲II
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) {
return 0;
}
int res = 1;
int cover = nums[0];
int i = 1;
while (i <= cover) {
if (cover >= nums.size() - 1) {
break;
}
int maxIndex = i;
int maxSteps = i + nums[i];
for (int j = i; j <= cover; j ++) {
if (j + nums[j] >= maxSteps) {
maxSteps = j + nums[j];
maxIndex = j;
}
}
i = maxIndex;
cover = maxSteps;
res ++;
}
return res;
}
};
1005.K次取反后最大化的數(shù)組和
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int i = 0;
for (i; i < nums.size() && nums[i] < 0 && k > 0; i ++) {
nums[i] *= -1;
k --;
}
if (k % 2 == 1) {
if (i == 0 || (i < nums.size() && abs(nums[i]) < abs(nums[i-1]))) {
nums[i] *= -1;
}
else {
nums[i-1] *= -1;
}
}
return accumulate(nums.begin(), nums.end(), 0);
}
};
