算法沉淀——贪心算法三
01.买卖股票的最佳时机 II
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
思路
通过画图我们不难看出上升区域利润如果都拿到手即为最大利润，这里有两种写法，一种是一次性加上一整段上升区域，另一种是计算每一小段上升区域
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret=0,n=prices.size();
for(int i=0;i<n;i++){
int j=i;
while(j+1<n&&prices[j+1]>prices[j]) j++;
ret+=prices[j]-prices[i];
i=j;
}
return ret;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret=0,n=prices.size();
for(int i=1;i<n;i++){
if(prices[i]>prices[i-1])
ret+=prices[i]-prices[i-1];
}
return ret;
}
};
02.K 次取反后最大化的数组和
题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标
i并将nums[i]替换为-nums[i]。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例 1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
示例 2：
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
提示：
1 <= nums.length <= 104-100 <= nums[i] <= 1001 <= k <= 104
思路
这里我们需要分情况讨论，设整个数组中负数的个数为m个：
1、m>k：把前k小的负数全变成正数
2、m==k：把所有的负数全变成正数；
3、m<k：先把负数变成正数；然后根据k-m的奇偶情况分情况讨论
代码
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int m=0,mini=INT_MAX,n=nums.size();
for(auto x:nums){
if(x<0) m++;
mini=min(mini,abs(x));
}
int ret=0;
if(m>k){
sort(nums.begin(),nums.end());
for(int i=0;i<k;i++) ret+=-nums[i];
for(int i=k;i<n;i++) ret+=nums[i];
}
else{
for(auto x:nums) ret+=abs(x);
if((k-m)%2) ret-=mini*2;
}
return ret;
}
};
03.按身高排序
题目链接：https://leetcode.cn/problems/sort-the-people/
给定一个字符串数组names和一个由不同正整数heights组成的数组。两个数组的长度都是n
对于每个索引i，names[i]和heights[i]表示该人的姓名和身高。
返回按人物身高降序names排序。
示例1：
输入： names = ["Mary","John","Emma"], heights = [180,165,170]
输出： ["Mary","Emma","John"]
解释： Mary 最高，其次是 Emma 和 John 。
示例2：
输入： names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出： ["Bob","Alice","Bob"]
解释：第一个 Bob 最高，其次是 Alice和第二个鲍勃。
限制条件：
n == names.length == heights.length1 <= n <= 1031 <= names[i].length <= 201 <= heights[i] <= 105names[i]由小写和大写英文字母组成。- 的所有值
heights都是不同的。
思路
这道题目并不是一道贪心题，但是可以为下一道贪心题提供思路，这里我们额外建立一个下标数组，相对于身高对下标数组进行排序，最后映射名字输出即可。
代码
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n=names.size();
vector<int> index(n);
for(int i=0;i<n;i++) index[i]=i;
sort(index.begin(),index.end(),[&](int i,int j){return heights[i]>heights[j];});
vector<string> ret;
for(int i:index) ret.push_back(names[i]);
return ret;
}
};
04.优势洗牌
题目链接：https://leetcode.cn/problems/advantage-shuffle/
给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]
示例 2：
输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]
提示：
1 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109
思路
当己方此时最差的比不过对面最差的时候，让我方最差的去处理掉对面最好的（反正要输，不如去拖掉对面⼀个最强的）；
当己方此时最差的能比得上对面最差的时候，就让两者比对下去（最差的都能获胜，为什么要输呢）。
每次决策，都会使我方处于优势
代码
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
sort(nums1.begin(),nums1.end());
vector<int> index(n);
for(int i=0;i<n;i++) index[i]=i;
sort(index.begin(),index.end(),[&](int i,int j){return nums2[i]<nums2[j];});
vector<int> ret(n);
int left=0,right=n-1;
for(auto x:nums1){
if(x>nums2[index[left]]) ret[index[left++]]=x;
else ret[index[right--]]=x;
}
return ret;
}
};