1005.K次取反后最大化的數(shù)組和

• 本題重點(diǎn)是邏輯問(wèn)題，同時(shí)復(fù)習(xí)static和sort的自定義操作與時(shí)間復(fù)雜度

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

• 選擇某個(gè)下標(biāo) i 并將 nums[i] 替換為 -nums[i] 。

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= k <= 10^4

思路

本題主要含義是，給出一個(gè)數(shù)組，基于這個(gè)數(shù)組在任意可重復(fù)的下標(biāo)做k次取反，計(jì)算k次取反后的最大和。

首先，數(shù)組內(nèi)有正數(shù)和負(fù)數(shù)，我們優(yōu)先對(duì)負(fù)數(shù)進(jìn)行取反。在負(fù)數(shù)里，我們又要優(yōu)先對(duì)絕對(duì)值最大的負(fù)數(shù)進(jìn)行取反。

當(dāng)負(fù)數(shù)全部取反，數(shù)組里全部是正數(shù)之后，此時(shí)次數(shù)還沒(méi)有用完，我們需要再優(yōu)先對(duì)絕對(duì)值最小的正數(shù)取反。

局部最優(yōu)就是，優(yōu)先找絕對(duì)值最大的負(fù)數(shù)/絕對(duì)值最小的正數(shù)取反。全局最優(yōu)就是最后的數(shù)組和最大。

本題實(shí)際上涉及到了兩次貪心。一次是數(shù)組有正有負(fù)，一次是數(shù)組里全是正數(shù)。

直接升序排序的寫(xiě)法

• 第一步：全部轉(zhuǎn)成正數(shù)
• 第二步：全轉(zhuǎn)成正數(shù)之后重新排序，因?yàn)?strong>轉(zhuǎn)成正數(shù)之后還有可能出現(xiàn)比現(xiàn)有正數(shù)更小的正數(shù)！

最開(kāi)始的寫(xiě)法：邏輯錯(cuò)誤

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        //先對(duì)數(shù)組進(jìn)行排序，這里可以考慮自定義比較函數(shù)，按照絕對(duì)值的大小進(jìn)行排序，也可以直接升序排序
        sort(nums.begin(),nums.end());
        int sum=0;
        for(int i=0;i<nums.size();i++){
            //cout<<nums[i]<<endl;
            if(nums[i]<0&&k>0){
                nums[i]=-nums[i];
                //cout<<nums[i]<<endl;
                k--;
                continue;
            }
            if(nums[i]>=0&&k>0){
                while(k>0){
                    nums[i]=-nums[i];
                    cout<<nums[i]<<endl;
                    k--;
                }   
            }
            //if(k==0) break;
        }
        for(int i=0;i<nums.size();i++){
            //cout<<nums[i]<<endl;
            sum += nums[i];
        }
        return sum;

    }
};

這種寫(xiě)法出現(xiàn)了邏輯錯(cuò)誤，原因是出現(xiàn)了如下案例：

本題中需要在最小的正數(shù)上面消耗次數(shù)，而不是把所有的負(fù)數(shù)轉(zhuǎn)正數(shù)之后，在原排序基礎(chǔ)上消耗原有的正數(shù)！

修改版

• 這種寫(xiě)法需要排序兩次，因?yàn)?strong>負(fù)數(shù)全轉(zhuǎn)成正數(shù)之后，很有可能出現(xiàn)更小的正數(shù)

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        //先對(duì)數(shù)組進(jìn)行排序，這里可以考慮自定義比較函數(shù)，按照絕對(duì)值的大小進(jìn)行排序，也可以直接升序排序
        sort(nums.begin(),nums.end());
        int sum=0;
        //先把所有負(fù)數(shù)轉(zhuǎn)成正數(shù)
        for(int i=0;i<nums.size();i++){
            //cout<<nums[i]<<endl;
            if(nums[i]<0&&k>0){
                nums[i]=-nums[i];
                //cout<<nums[i]<<endl;
                k--;
            }
        }
        //再重新排序，并在重排后的第一個(gè)元素上消耗剩余所有次數(shù)
        sort(nums.begin(),nums.end());
        while(k>0){
            nums[0]=-nums[0];
            k--;
        }
        //求和
        for(int i=0;i<nums.size();i++){
            cout<<nums[i]<<endl;
            sum += nums[i];
        }
        return sum;

    }
};

時(shí)間復(fù)雜度

這種寫(xiě)法需要排序兩次，時(shí)間復(fù)雜度主要取決于sort的復(fù)雜度。

在C++中，sort函數(shù)的時(shí)間復(fù)雜度是O(nlogn)，其中n是數(shù)組的長(zhǎng)度。因此，上述代碼的時(shí)間復(fù)雜度是O(nlogn)（對(duì)原數(shù)組排序）+ O(n)（遍歷數(shù)組對(duì)負(fù)數(shù)進(jìn)行操作）+ O(nlogn)（再次對(duì)數(shù)組排序）+ O(n)（對(duì)剩余的k進(jìn)行處理和求和）= O(nlogn)。

實(shí)際上，時(shí)間復(fù)雜度為O(nlogn + nk)，先進(jìn)行了一次全體元素的排序（O(nlogn)），然后可能對(duì)每個(gè)元素進(jìn)行多次操作（O(nk)）。

排序次數(shù)過(guò)多導(dǎo)致開(kāi)銷會(huì)增大。此時(shí)我們考慮優(yōu)化。

自定義sort對(duì)絕對(duì)值排序的寫(xiě)法

• 這種寫(xiě)法，我們?cè)谝婚_(kāi)始，就對(duì)元素絕對(duì)值進(jìn)行排序。
• 注意絕對(duì)值排序一定要降序排序！因?yàn)槲覀円?strong>先消耗數(shù)值大的負(fù)數(shù)！sort本身是升序，只用sort的話數(shù)值大的負(fù)數(shù)會(huì)在前面，但是這里自定義了絕對(duì)值，就必須把數(shù)值大的放在前面，用**greater(降序)**來(lái)實(shí)現(xiàn)！

class Solution {
public:
    int sum=0;
    static bool cmp(int a,int b){
        if(abs(a)>abs(b)) 
            return true;//絕對(duì)值降序排序，因?yàn)橐忍幚泶蟮呢?fù)數(shù)
        else 
           return false;
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
       sort(nums.begin(),nums.end(),cmp);//絕對(duì)值降序排序
       for(int i=0;i<nums.size();i++){
           //第一次遍歷的時(shí)候，只在負(fù)數(shù)上消耗次數(shù)！
           if(nums[i]<0&&k>0){
               nums[i]=-nums[i];
               k--;
           }
          if(k==0) break;
       }
       //如果此時(shí)還有k沒(méi)消耗完，看看k是奇數(shù)or偶數(shù)，如果是偶數(shù)就不用管了
       if(k%2==1){
           //如果是奇數(shù)，直接最小值取反就是結(jié)果
           nums[nums.size()-1]= - nums[nums.size()-1];
       }
       for(int i:nums){//遍歷Nums
           sum+=i;  //這種寫(xiě)法，i就是元素本身，不能寫(xiě)成nums[i]否則會(huì)越界
       }
        return sum;
    }
};

sort的自定義比較函數(shù)cmp必須聲明為static的原因

c++靜態(tài)變量成員函數(shù)和全局函數(shù)的區(qū)別_成員函數(shù)全局函數(shù)_大磕學(xué)家ZYX的博客-CSDN博客

cmp函數(shù)被聲明為static，這是因?yàn)?strong>std::sort需要一個(gè)能夠在全局訪問(wèn)的函數(shù)，或者一個(gè)lambda函數(shù)。

如果cmp不是static的，那么這就意味著它需要一個(gè)對(duì)象上下文（因?yàn)榉庆o態(tài)成員函數(shù)都有一個(gè)隱含的this指針參數(shù)）。然而在這種情況下，我們不能給出這樣一個(gè)上下文。所以，我們需要使cmp函數(shù)成為一個(gè)靜態(tài)成員函數(shù)，這樣它就可以在沒(méi)有對(duì)象上下文的情況下被調(diào)用。

static的用法補(bǔ)充：static在 C++ 中的四種用法_大磕學(xué)家ZYX的博客-CSDN博客

std::sort升降序的問(wèn)題（默認(rèn)升序）

注意，在C++中，std::sort函數(shù)默認(rèn)的排序方式是從小到大，也就是升序排序。這個(gè)函數(shù)會(huì)對(duì)輸入范圍內(nèi)的元素進(jìn)行排序，使得排序后的元素序列是非遞減的。

如果要實(shí)現(xiàn)降序排序，你可以給std::sort函數(shù)提供第三個(gè)參數(shù)，即一個(gè)自定義的比較函數(shù)或者lambda表達(dá)式。這個(gè)比較函數(shù)定義了兩個(gè)元素的比較規(guī)則。

例如，如果想對(duì)candidates數(shù)組進(jìn)行降序排序，你可以這樣做：

std::sort(candidates.begin(), candidates.end(), std::greater<int>());

在這個(gè)代碼中，std::greater<int>()是一個(gè)函數(shù)對(duì)象，它定義了一個(gè)規(guī)則，使得sort函數(shù)會(huì)按照這個(gè)規(guī)則進(jìn)行排序，也就是降序排序。

另一種方式是使用lambda表達(dá)式來(lái)定義比較規(guī)則：

std::sort(candidates.begin(), candidates.end(), [](int a, int b) {return a > b;});

在這個(gè)代碼中，[](int a, int b) {return a > b;}是一個(gè)lambda表達(dá)式，它接受兩個(gè)參數(shù)a和b，如果a > b，則返回true，這樣sort函數(shù)就會(huì)按照這個(gè)規(guī)則進(jìn)行降序排序。

時(shí)間復(fù)雜度

優(yōu)化寫(xiě)法時(shí)間復(fù)雜度同樣主要取決于排序的復(fù)雜度，即O(nlogn)。遍歷數(shù)組進(jìn)行操作的時(shí)間復(fù)雜度是O(n)。所以總的時(shí)間復(fù)雜度是O(nlogn)。

總結(jié)

第二種寫(xiě)法的優(yōu)化主要體現(xiàn)在兩個(gè)地方：

1. 通過(guò)使用絕對(duì)值的大小進(jìn)行排序，可以優(yōu)先處理絕對(duì)值大的元素。這樣，不僅可以減少不必要的符號(hào)反轉(zhuǎn)操作，而且可以更好地利用操作次數(shù)，因?yàn)閷?duì)絕對(duì)值大的元素進(jìn)行反轉(zhuǎn)，可以獲得更大的結(jié)果。
2. 通過(guò)在第一次遍歷中只在負(fù)數(shù)上消耗次數(shù)，并在處理完所有負(fù)數(shù)后，不需要再次進(jìn)行排序，因?yàn)榇藭r(shí)已經(jīng)是從小到大的正數(shù)順序（本來(lái)就是絕對(duì)值排序）。再根據(jù)剩余次數(shù)的奇偶性進(jìn)行相應(yīng)操作，可以避免對(duì)每個(gè)元素進(jìn)行多次操作，進(jìn)一步降低時(shí)間復(fù)雜度。
3. sort升序的寫(xiě)法和絕對(duì)值降序的寫(xiě)法如下圖所示。局部最優(yōu)：讓絕對(duì)值大的負(fù)數(shù)變?yōu)檎龜?shù)，當(dāng)前數(shù)值達(dá)到最大，整體最優(yōu)：整個(gè)數(shù)組和達(dá)到最大。

134.加油站

• 本題可以和 53.最大子數(shù)組和 放在一起來(lái)看，都是屬于遇到了不需要的結(jié)果，直接統(tǒng)計(jì)量清零，重新開(kāi)始算起點(diǎn)的類型。

在一條環(huán)路上有 n 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升。

你有一輛油箱容量無(wú)限的的汽車，從第 i 個(gè)加油站開(kāi)往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)，開(kāi)始時(shí)油箱為空。

給定兩個(gè)整數(shù)數(shù)組 gas 和 cost ，如果你可以按順序繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。

示例 1:

輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號(hào)加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開(kāi)往 4 號(hào)加油站，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開(kāi)往 0 號(hào)加油站，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開(kāi)往 1 號(hào)加油站，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開(kāi)往 2 號(hào)加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開(kāi)往 3 號(hào)加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號(hào)加油站。
因此，3 可為起始索引。

示例 2:

輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號(hào)或 1 號(hào)加油站出發(fā)，因?yàn)闆](méi)有足夠的汽油可以讓你行駛到下一個(gè)加油站。
我們從 2 號(hào)加油站出發(fā)，可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開(kāi)往 0 號(hào)加油站，此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開(kāi)往 1 號(hào)加油站，此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無(wú)法返回 2 號(hào)加油站，因?yàn)榉党绦枰?4 升汽油，但是你的油箱只有 3 升汽油。
因此，無(wú)論怎樣，你都不可能繞環(huán)路行駛一周。

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

思路

本題是模擬加油站跑圈的過(guò)程，每到一個(gè)站點(diǎn)補(bǔ)充油，開(kāi)到下一個(gè)站點(diǎn)消耗油。需要讓目前的油+補(bǔ)充油高于消耗油，才能開(kāi)到下一個(gè)站點(diǎn)。大致情況如圖：

本題的暴力解法是兩個(gè)for循環(huán)，一個(gè)循環(huán)模擬每個(gè)站點(diǎn)作為起始位置的情況，一個(gè)循環(huán)看這個(gè)位置能不能跑一圈，時(shí)間復(fù)雜度就是n^2。暴力解思路簡(jiǎn)單，但是跑一圈的過(guò)程不太好做。while模擬轉(zhuǎn)圈過(guò)程比較復(fù)雜！

本題最好還是貪心的思路來(lái)解。本題有補(bǔ)充+消耗，我們要看的就是對(duì)油箱是增加作用還是消耗作用。也就是統(tǒng)計(jì)凈增長(zhǎng)量。如下圖所示。

我們用curSum變量去累積每個(gè)站點(diǎn)油箱的狀態(tài)。

一旦油箱在這個(gè)站點(diǎn)狀態(tài)成為負(fù)數(shù)，說(shuō)明從這個(gè)位置之前的任意位置開(kāi)始，都不可能到達(dá)終點(diǎn)！此時(shí)我們直接選擇負(fù)數(shù)狀態(tài)位置的i+1作為新的起始點(diǎn)，之前的起始點(diǎn)就全部拋棄掉。

遇到i位置的curSum<0，就直接讓i+1作為起點(diǎn)，這種邏輯是否正確可以畫(huà)圖來(lái)看：

貪心的思路就是不斷累加curSum，局部最優(yōu)：當(dāng)前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因?yàn)閺膇之前開(kāi)始一定不行。全局最優(yōu)：找到可以跑一圈的起始位置。

局部最優(yōu)可以推出全局最優(yōu)并且想不出來(lái)反例，反例在上圖有大概的證明，因此可以嘗試貪心。

完整版

• 和 53.最大子數(shù)組和 一樣，本題同樣也不需要改變for的遍歷方式！startIndex只是用來(lái)記錄位置方便返回，實(shí)際上重新開(kāi)始遍歷的時(shí)候，只需要把統(tǒng)計(jì)量curSum置零就可以了！
• 凈增長(zhǎng)量如果<0，說(shuō)明此時(shí)油箱狀態(tài)成了負(fù)數(shù)，也就是說(shuō)在此位置之前的點(diǎn)，都不可能跑完一圈；此時(shí)應(yīng)重新置零，開(kāi)始統(tǒng)計(jì)新的凈增長(zhǎng)，直到凈增長(zhǎng)量不是0，才說(shuō)明能夠跑完一圈

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum=0;
        int totalSum=0;//統(tǒng)計(jì)所有的rest，看是不是全是負(fù)數(shù)，全是負(fù)數(shù)說(shuō)明不可能跑完一圈
        for(int i=0;i<gas.size();i++){
            totalSum+=(gas[i]-cost[i]);
        }
        //如果凈增長(zhǎng)到最后都是負(fù)數(shù)，返回-1
        if(totalSum<0)  return -1;
        
        int startIndex=0;//記錄i+1作為起始位置，找到合適的起始i
        for(int i=0;i<gas.size();i++){
            curSum += (gas[i]-cost[i]);//統(tǒng)計(jì)剩余油量
            if(curSum<0){//i之前的油量rest累加為負(fù)數(shù)
                startIndex=i+1;
                curSum=0;//重新置零，開(kāi)始統(tǒng)計(jì)新的凈增長(zhǎng)，直到最后凈增長(zhǎng)量不是0，才說(shuō)明能夠跑完一圈
            }
        }
		return startIndex;
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

總結(jié)

貪心的主要策略就是局部最優(yōu)可以推出全局最優(yōu)，進(jìn)而求得起始位置。本題和 53.最大子數(shù)組和 都屬于遇到了不需要結(jié)果，直接重置統(tǒng)計(jì)量，相當(dāng)于重置起點(diǎn)的類型。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-536247.html

到了這里，關(guān)于DAY38：貪心算法（五）K次取反后最大數(shù)組和+加油站的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！