01.買賣股票的最佳時機 II

題目鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

給你一個整數(shù)數(shù)組 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 * 104
• 0 <= prices[i] <= 104

思路

通過畫圖我們不難看出上升區(qū)域利潤如果都拿到手即為最大利潤，這里有兩種寫法，一種是一次性加上一整段上升區(qū)域，另一種是計算每一小段上升區(qū)域

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-842823.html

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 次取反后最大化的數(shù)組和

題目鏈接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，按以下方法修改該數(shù)組：

• 選擇某個下標 i 并將 nums[i] 替換為 -nums[i] 。

重復(fù)這個過程恰好 k 次?？梢远啻芜x擇同一個下標 i 。

以這種方式修改數(shù)組后，返回數(shù)組 可能的最大和 。

示例 1：

輸入：nums = [4,2,3], k = 1
輸出：5
解釋：選擇下標 1 ，nums 變?yōu)?[4,-2,3] 。

示例 2：

輸入：nums = [3,-1,0,2], k = 3
輸出：6
解釋：選擇下標 (1, 2, 2) ，nums 變?yōu)?[3,1,0,2] 。

示例 3：

輸入：nums = [2,-3,-1,5,-4], k = 2
輸出：13
解釋：選擇下標 (1, 4) ，nums 變?yōu)?[2,3,-1,5,4] 。 

提示：

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104

思路

這里我們需要分情況討論，設(shè)整個數(shù)組中負數(shù)的個數(shù)為m個：

1、m>k：把前k小的負數(shù)全變成正數(shù)
2、m==k：把所有的負數(shù)全變成正數(shù)；
3、m<k：先把負數(shù)變成正數(shù)；然后根據(jù)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/

給定一個字符串數(shù)組names和一個由不同正整數(shù)heights組成的數(shù)組。兩個數(shù)組的長度都是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.length
• 1 <= n <= 103
• 1 <= names[i].length <= 20
• 1 <= heights[i] <= 105
• names[i]由小寫和大寫英文字母組成。
• 的所有值heights都是不同的。

思路

這道題目并不是一道貪心題，但是可以為下一道貪心題提供思路，這里我們額外建立一個下標數(shù)組，相對于身高對下標數(shù)組進行排序，最后映射名字輸出即可。

代碼

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.優(yōu)勢洗牌

題目鏈接：https://leetcode.cn/problems/advantage-shuffle/

給定兩個長度相等的數(shù)組 nums1 和 nums2，nums1 相對于 nums2 的優(yōu)勢可以用滿足 nums1[i] > nums2[i] 的索引 i 的數(shù)目來描述。

返回 nums1 的任意排列，使其相對于 nums2 的優(yōu)勢最大化。

示例 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 <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 109

思路

當己方此時最差的比不過對面最差的時候，讓我方最差的去處理掉對面最好的（反正要輸，不如去拖掉對面?個最強的）；
當己方此時最差的能比得上對面最差的時候，就讓兩者比對下去（最差的都能獲勝，為什么要輸呢）。
每次決策，都會使我方處于優(yōu)勢

代碼

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;
    }
};

到了這里，關(guān)于算法沉淀——貪心算法三（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！