国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ))

這篇具有很好參考價(jià)值的文章主要介紹了第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ))。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方,請(qǐng)大家不吝賜教,您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

本文章代碼以c++為例!

一、力扣第1005題:K 次取反后最大化的數(shù)組和

題目:

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

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

重復(fù)這個(gè)過程恰好 k 次。可以多次選擇同一個(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 <= 104
  • -100 <= nums[i] <= 100
  • 1 <= k <= 104

思路

本題思路其實(shí)比較好想了,如何可以讓數(shù)組和最大呢?

貪心的思路,局部最優(yōu):讓絕對(duì)值大的負(fù)數(shù)變?yōu)檎龜?shù),當(dāng)前數(shù)值達(dá)到最大,整體最優(yōu):整個(gè)數(shù)組和達(dá)到最大。

局部最優(yōu)可以推出全局最優(yōu)。

那么如果將負(fù)數(shù)都轉(zhuǎn)變?yōu)檎龜?shù)了,K依然大于0,此時(shí)的問題是一個(gè)有序正整數(shù)序列,如何轉(zhuǎn)變K次正負(fù),讓 數(shù)組和 達(dá)到最大。

那么又是一個(gè)貪心:局部最優(yōu):只找數(shù)值最小的正整數(shù)進(jìn)行反轉(zhuǎn),當(dāng)前數(shù)值和可以達(dá)到最大(例如正整數(shù)數(shù)組{5, 3, 1},反轉(zhuǎn)1 得到-1 比 反轉(zhuǎn)5得到的-5 大多了),全局最優(yōu):整個(gè) 數(shù)組和 達(dá)到最大。

雖然這道題目大家做的時(shí)候,可能都不會(huì)去想什么貪心算法,一鼓作氣,就AC了。

我這里其實(shí)是為了給大家展現(xiàn)出來 經(jīng)常被大家忽略的貪心思路,這么一道簡(jiǎn)單題,就用了兩次貪心!

那么本題的解題步驟為:

  • 第一步:將數(shù)組按照絕對(duì)值大小從大到小排序,注意要按照絕對(duì)值的大小
  • 第二步:從前向后遍歷,遇到負(fù)數(shù)將其變?yōu)檎龜?shù),同時(shí)K--
  • 第三步:如果K還大于0,那么反復(fù)轉(zhuǎn)變數(shù)值最小的元素,將K用完
  • 第四步:求和

對(duì)應(yīng)C++代碼如下:

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};
  • 時(shí)間復(fù)雜度: O(nlogn)
  • 空間復(fù)雜度: O(1)

# 總結(jié)

貪心的題目如果簡(jiǎn)單起來,會(huì)讓人簡(jiǎn)單到開始懷疑:本來不就應(yīng)該這么做么?這也算是算法?我認(rèn)為這不是貪心?

本題其實(shí)很簡(jiǎn)單,不會(huì)貪心算法的同學(xué)都可以做出來,但是我還是全程用貪心的思路來講解。

因?yàn)樨澬牡乃伎挤绞揭欢ㄒ校?/p>

如果沒有貪心的思考方式(局部最優(yōu),全局最優(yōu)),很容易陷入貪心簡(jiǎn)單題憑感覺做,貪心難題直接不會(huì)做,其實(shí)這樣就鍛煉不了貪心的思考方式了。

所以明知道是貪心簡(jiǎn)單題,也要靠貪心的思考方式來解題,這樣對(duì)培養(yǎng)解題感覺很有幫助。

二、力扣第134題:加油站

題目:

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

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

給定兩個(gè)整數(shù)數(shù)組 gascost ,如果你可以按順序繞環(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 升汽油
開往 4 號(hào)加油站,此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號(hào)加油站,此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號(hào)加油站,此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號(hào)加油站,此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開往 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)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站。
我們從 2 號(hào)加油站出發(fā),可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 0 號(hào)加油站,此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號(hào)加油站,此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號(hào)加油站,因?yàn)榉党绦枰?4 升汽油,但是你的油箱只有 3 升汽油。
因此,無論怎樣,你都不可能繞環(huán)路行駛一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

思路

# 暴力方法

暴力的方法很明顯就是O(n^2)的,遍歷每一個(gè)加油站為起點(diǎn)的情況,模擬一圈。

如果跑了一圈,中途沒有斷油,而且最后油量大于等于0,說明這個(gè)起點(diǎn)是ok的。

暴力的方法思路比較簡(jiǎn)單,但代碼寫起來也不是很容易,關(guān)鍵是要模擬跑一圈的過程。

for循環(huán)適合模擬從頭到尾的遍歷,而while循環(huán)適合模擬環(huán)形遍歷,要善于使用while!

C++代碼如下:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 記錄剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) { // 模擬以i為起點(diǎn)行駛一圈(如果有rest==0,那么答案就不唯一了)
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i為起點(diǎn)跑一圈,剩余油量>=0,返回該起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

問題是:有多個(gè)加油站形成一個(gè)環(huán)形路線,每個(gè)加油站都有一個(gè)固定的油量(gas數(shù)組)和從當(dāng)前加油站開到下一個(gè)加油站所需要的油量(cost數(shù)組)。問從哪個(gè)加油站出發(fā),可以走完整個(gè)環(huán)形路線。如果不能從任何一個(gè)加油站出發(fā)走完整個(gè)環(huán)形,返回-1。

代碼解析:

  1. 外層循環(huán)for (int i = 0; i < cost.size(); i++)?- 遍歷所有加油站,考慮每一個(gè)加油站作為起點(diǎn)。

  2. int rest = gas[i] - cost[i];?-?rest?記錄從當(dāng)前加油站出發(fā)后的剩余油量。初始值是當(dāng)前加油站的油量減去開到下一個(gè)加油站所需的油量。

  3. int index = (i + 1) % cost.size();?- 初始化一個(gè)index,它表示從第i個(gè)加油站出發(fā)后下一個(gè)要到達(dá)的加油站的位置。這里使用了取模操作,確保index在數(shù)組的范圍內(nèi)。

  4. 內(nèi)層循環(huán)while (rest > 0 && index != i)?- 當(dāng)剩余的油量為正且沒有回到起點(diǎn)時(shí),繼續(xù)模擬行駛。

    • rest += gas[index] - cost[index];?- 更新剩余油量,加上在下一個(gè)加油站獲得的油量并減去開往再下一個(gè)加油站所需的油量。

    • index = (index + 1) % cost.size();?- 移動(dòng)到下一個(gè)加油站。

  5. 判斷條件if (rest >= 0 && index == i)?- 如果剩余油量不為負(fù)且回到了出發(fā)的加油站,則找到了一個(gè)滿足條件的起始位置。

  6. 如果所有的加油站都作為起點(diǎn)嘗試過后都不能滿足條件,返回-1。

這個(gè)算法的基本思想是,對(duì)于每一個(gè)加油站,都嘗試從它開始走一圈看是否可行。如果某個(gè)加油站作為起點(diǎn)走不通,則說明它到下一個(gè)加油站之間的任何一個(gè)加油站都不能作為起點(diǎn)。因?yàn)槿绻渲幸粋€(gè)可以作為起點(diǎn),則前一個(gè)加油站也可以。所以,當(dāng)找到一個(gè)加油站不能作為起點(diǎn)時(shí),可以直接跳過它到下一個(gè)加油站之間的所有加油站,繼續(xù)嘗試下一個(gè)。

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

# 貪心算法(方法一)

直接從全局進(jìn)行貪心選擇,情況如下:

  • 情況一:如果gas的總和小于cost總和,那么無論從哪里出發(fā),一定是跑不了一圈的

  • 情況二:rest[i] = gas[i]-cost[i]為一天剩下的油,i從0開始計(jì)算累加到最后一站,如果累加沒有出現(xiàn)負(fù)數(shù),說明從0出發(fā),油就沒有斷過,那么0就是起點(diǎn)。

  • 情況三:如果累加的最小值是負(fù)數(shù),汽車就要從非0節(jié)點(diǎn)出發(fā),從后向前,看哪個(gè)節(jié)點(diǎn)能把這個(gè)負(fù)數(shù)填平,能把這個(gè)負(fù)數(shù)填平的節(jié)點(diǎn)就是出發(fā)節(jié)點(diǎn)。

C++代碼如下:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX; // 從起點(diǎn)出發(fā),油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情況1
        if (min >= 0) return 0;     // 情況2
                                    // 情況3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

這是一個(gè)優(yōu)化版本的解決方案,用于解決同樣的「加油站環(huán)形路線」問題。這個(gè)版本的算法使用了貪心的思想,通過一次遍歷來確定從哪個(gè)加油站出發(fā)可以完成整個(gè)環(huán)形路線。

代碼解析:

  1. 初始化兩個(gè)變量:

    • curSum:用于記錄從起點(diǎn)出發(fā),油箱里的油量累計(jì)值。
    • min:用于記錄從起點(diǎn)出發(fā),油箱里的油量最小值。
  2. 第一個(gè)循環(huán):for (int i = 0; i < gas.size(); i++)?- 遍歷所有加油站,計(jì)算從起點(diǎn)出發(fā)到每個(gè)加油站的油量累計(jì)值,并更新curSummin。

  3. if (curSum < 0) return -1;?- 如果curSum為負(fù),說明油的總量不足以支撐整個(gè)環(huán)形路線,直接返回-1。

  4. if (min >= 0) return 0;?- 如果min為非負(fù),說明從第0個(gè)加油站出發(fā),油箱里的油量始終為非負(fù),因此可以從第0個(gè)加油站出發(fā)完成整個(gè)環(huán)形路線。

  5. 第二個(gè)循環(huán):for (int i = gas.size() - 1; i >= 0; i--)?- 如果上述兩種情況都不滿足,從最后一個(gè)加油站開始反向遍歷。這是因?yàn)?,如果從?個(gè)加油站出發(fā)在某個(gè)加油站油量最少(即min),那么從這個(gè)加油站的下一個(gè)加油站出發(fā)可能是一個(gè)合適的起點(diǎn)。

  6. 在第二個(gè)循環(huán)中,每次都更新min的值,并檢查min是否為非負(fù)。如果為非負(fù),說明從當(dāng)前加油站出發(fā)可以完成整個(gè)環(huán)形路線。

  7. 如果所有的加油站都嘗試過后都不滿足條件,返回-1。

這個(gè)算法的基本思想是,首先檢查總的油量是否足夠支撐整個(gè)環(huán)形路線,然后找到從哪個(gè)加油站出發(fā)油箱里的油量最少。如果這個(gè)最小值為非負(fù),說明可以從第0個(gè)加油站出發(fā);否則,從這個(gè)最小值對(duì)應(yīng)的加油站的下一個(gè)加油站開始嘗試,直到找到一個(gè)合適的起點(diǎn)或者遍歷完所有的加油站。

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

其實(shí)我不認(rèn)為這種方式是貪心算法,因?yàn)闆]有找出局部最優(yōu),而是直接從全局最優(yōu)的角度上思考問題。

但這種解法又說不出是什么方法,這就是一個(gè)從全局角度選取最優(yōu)解的模擬操作。

所以對(duì)于本解法是貪心,我持保留意見!

但不管怎么說,解法畢竟還是巧妙的,不用過于執(zhí)著于其名字稱呼。

# 貪心算法(方法二)

可以換一個(gè)思路,首先如果總油量減去總消耗大于等于零那么一定可以跑完一圈,說明 各個(gè)站點(diǎn)的加油站 剩油量rest[i]相加一定是大于等于零的。

每個(gè)加油站的剩余量rest[i]為gas[i] - cost[i]。

i從0開始累加rest[i],和記為curSum,一旦curSum小于零,說明[0, i]區(qū)間都不能作為起始位置,因?yàn)檫@個(gè)區(qū)間選擇任何一個(gè)位置作為起點(diǎn),到i這里都會(huì)斷油,那么起始位置從i+1算起,再?gòu)?計(jì)算curSum。

如圖:

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ)),算法,數(shù)據(jù)結(jié)構(gòu),leetcode,c++

那么為什么一旦[0,i] 區(qū)間和為負(fù)數(shù),起始位置就可以是i+1呢,i+1后面就不會(huì)出現(xiàn)更大的負(fù)數(shù)?

如果出現(xiàn)更大的負(fù)數(shù),就是更新i,那么起始位置又變成新的i+1了。

那有沒有可能 [0,i] 區(qū)間 選某一個(gè)作為起點(diǎn),累加到 i這里 curSum是不會(huì)小于零呢? 如圖:

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ)),算法,數(shù)據(jù)結(jié)構(gòu),leetcode,c++

如果 curSum<0 說明 區(qū)間和1 + 區(qū)間和2 < 0, 那么 假設(shè)從上圖中的位置開始計(jì)數(shù)curSum不會(huì)小于0的話,就是 區(qū)間和2>0。

區(qū)間和1 + 區(qū)間和2 < 0 同時(shí) 區(qū)間和2>0,只能說明區(qū)間和1 < 0, 那么就會(huì)從假設(shè)的箭頭初就開始從新選擇其實(shí)位置了。

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

局部最優(yōu)可以推出全局最優(yōu),找不出反例,試試貪心!

C++代碼如下:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 當(dāng)前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新為i+1
                curSum = 0;     // curSum從0開始
            }
        }
        if (totalSum < 0) return -1; // 說明怎么走都不可能跑一圈了
        return start;
    }
};
  • 時(shí)間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(1)

說這種解法為貪心算法,才是有理有據(jù)的,因?yàn)槿肿顑?yōu)解是根據(jù)局部最優(yōu)推導(dǎo)出來的。

# 總結(jié)

對(duì)于本題首先給出了暴力解法,暴力解法模擬跑一圈的過程其實(shí)比較考驗(yàn)代碼技巧的,要對(duì)while使用的很熟練。

然后給出了兩種貪心算法,對(duì)于第一種貪心方法,其實(shí)我認(rèn)為就是一種直接從全局選取最優(yōu)的模擬操作,思路還是很巧妙的,值得學(xué)習(xí)一下。

對(duì)于第二種貪心方法,才真正體現(xiàn)出貪心的精髓,用局部最優(yōu)可以推出全局最優(yōu),進(jìn)而求得起始位置。

三、力扣第135題:分發(fā)糖果

題目:

n 個(gè)孩子站成一排。給你一個(gè)整數(shù)數(shù)組 ratings 表示每個(gè)孩子的評(píng)分。

你需要按照以下要求,給這些孩子分發(fā)糖果:

  • 每個(gè)孩子至少分配到 1 個(gè)糖果。
  • 相鄰兩個(gè)孩子評(píng)分更高的孩子會(huì)獲得更多的糖果。

請(qǐng)你給每個(gè)孩子分發(fā)糖果,計(jì)算并返回需要準(zhǔn)備的 最少糖果數(shù)目 。

示例?1:

輸入:ratings = [1,0,2]
輸出:5
解釋:你可以分別給第一個(gè)、第二個(gè)、第三個(gè)孩子分發(fā) 2、1、2 顆糖果。

示例?2:

輸入:ratings = [1,2,2]
輸出:4
解釋:你可以分別給第一個(gè)、第二個(gè)、第三個(gè)孩子分發(fā) 1、2、1 顆糖果。
     第三個(gè)孩子只得到 1 顆糖果,這滿足題面中的兩個(gè)條件。

提示:

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

思路

這道題目一定是要確定一邊之后,再確定另一邊,例如比較每一個(gè)孩子的左邊,然后再比較右邊,如果兩邊一起考慮一定會(huì)顧此失彼。

先確定右邊評(píng)分大于左邊的情況(也就是從前向后遍歷)

此時(shí)局部最優(yōu):只要右邊評(píng)分比左邊大,右邊的孩子就多一個(gè)糖果,全局最優(yōu):相鄰的孩子中,評(píng)分高的右孩子獲得比左邊孩子更多的糖果

局部最優(yōu)可以推出全局最優(yōu)。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一個(gè),所以貪心:candyVec[i] = candyVec[i - 1] + 1

代碼如下:

// 從前向后
for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

如圖:

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ)),算法,數(shù)據(jù)結(jié)構(gòu),leetcode,c++

再確定左孩子大于右孩子的情況(從后向前遍歷)

遍歷順序這里有同學(xué)可能會(huì)有疑問,為什么不能從前向后遍歷呢?

因?yàn)?rating[5]與rating[4]的比較 要利用上 rating[5]與rating[6]的比較結(jié)果,所以 要從后向前遍歷。

如果從前向后遍歷,rating[5]與rating[4]的比較 就不能用上 rating[5]與rating[6]的比較結(jié)果了 。如圖:

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ)),算法,數(shù)據(jù)結(jié)構(gòu),leetcode,c++

所以確定左孩子大于右孩子的情況一定要從后向前遍歷!

如果 ratings[i] > ratings[i + 1],此時(shí)candyVec[i](第i個(gè)小孩的糖果數(shù)量)就有兩個(gè)選擇了,一個(gè)是candyVec[i + 1] + 1(從右邊這個(gè)加1得到的糖果數(shù)量),一個(gè)是candyVec[i](之前比較右孩子大于左孩子得到的糖果數(shù)量)。

那么又要貪心了,局部最優(yōu):取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數(shù)量,保證第i個(gè)小孩的糖果數(shù)量既大于左邊的也大于右邊的。全局最優(yōu):相鄰的孩子中,評(píng)分高的孩子獲得更多的糖果。

局部最優(yōu)可以推出全局最優(yōu)。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數(shù)量,candyVec[i]只有取最大的才能既保持對(duì)左邊candyVec[i - 1]的糖果多,也比右邊candyVec[i + 1]的糖果多

如圖:

第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ)),算法,數(shù)據(jù)結(jié)構(gòu),leetcode,c++

所以該過程代碼如下:

// 從后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1] ) {
        candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
    }
}

整體代碼如下:

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 從前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 從后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 統(tǒng)計(jì)結(jié)果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};
  • 時(shí)間復(fù)雜度: O(n)
  • 空間復(fù)雜度: O(n)

# 總結(jié)

這在leetcode上是一道困難的題目,其難點(diǎn)就在于貪心的策略,如果在考慮局部的時(shí)候想兩邊兼顧,就會(huì)顧此失彼。

那么本題我采用了兩次貪心的策略:

  • 一次是從左到右遍歷,只比較右邊孩子評(píng)分比左邊大的情況。
  • 一次是從右到左遍歷,只比較左邊孩子評(píng)分比右邊大的情況。

這樣從局部最優(yōu)推出了全局最優(yōu),即:相鄰的孩子中,評(píng)分高的孩子獲得更多的糖果。

day34補(bǔ)文章來源地址http://www.zghlxwxcb.cn/news/detail-679937.html

到了這里,關(guān)于第八章 貪心算法 part03 1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果 (day34補(bǔ))的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!

本文來自互聯(lián)網(wǎng)用戶投稿,該文觀點(diǎn)僅代表作者本人,不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù),不擁有所有權(quán),不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載,請(qǐng)注明出處: 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符,請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋,一經(jīng)查實(shí),立即刪除!

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

  • 算法 貪心3 || 1005. K 次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果

    算法 貪心3 || 1005. K 次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果

    思路: 給數(shù)組按照絕對(duì)值大小排序 ,優(yōu)先將負(fù)數(shù)轉(zhuǎn)成正數(shù)。如果此時(shí) k % 2 == 1 。最后再將 絕對(duì)值最小的值變成負(fù)數(shù) (該值可能原本是負(fù)數(shù)) 而不是直接從小到大排序。 例如-8,-5,-5,-3,-2,9這種序列。如果直接從小到大排序,那么最后一個(gè)變符號(hào)的就會(huì)是9,但其實(shí)讓

    2023年04月12日
    瀏覽(49)
  • K 次取反后最大化的數(shù)組和【貪心算法】

    K 次取反后最大化的數(shù)組和【貪心算法】

    1005 . K 次取反后最大化的數(shù)組和 給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ,按以下方法修改該數(shù)組: 選擇某個(gè)下標(biāo) i 并將 nums[i] 替換為 -nums[i] 。 重復(fù)這個(gè)過程恰好 k 次??梢远啻芜x擇同一個(gè)下標(biāo) i 。 以這種方式修改數(shù)組后,返回?cái)?shù)組 可能的最大和 。 關(guān)于 nums = IntStream.of(nums

    2024年02月11日
    瀏覽(29)
  • 力扣 1005. K 次取反后最大化的數(shù)組和

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

    題目來源:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ C++題解1:最直接的想法就是負(fù)的變正的,如果負(fù)的元素?cái)?shù)量小于k,就挑選絕對(duì)值大的負(fù)數(shù)變正;如果負(fù)的元素?cái)?shù)量大于k,那么還需要根據(jù)剩下的k(待變換數(shù))的奇偶性來判斷,偶數(shù)就不用管了,奇數(shù)

    2024年02月16日
    瀏覽(36)
  • DAY38:貪心算法(五)K次取反后最大數(shù)組和+加油站

    DAY38:貪心算法(五)K次取反后最大數(shù)組和+加油站

    本題重點(diǎ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è)過程恰好 k 次。可以多次選擇同一個(gè)下標(biāo) i 。 以這種方式修改數(shù)組后,返回?cái)?shù)組 可能的

    2024年02月13日
    瀏覽(25)
  • 【隨想錄】Day34—第八章 貪心算法 part03

    【隨想錄】Day34—第八章 貪心算法 part03

    題目鏈接:1005. K 次取反后最大化的數(shù)組和 貪心思路 : 先對(duì)數(shù)組中的元素進(jìn)行排序 遍歷數(shù)組,如果 當(dāng)前遍歷的位置值 0 k0 直接變號(hào),之后對(duì) k 進(jìn)行 -- 如果不小于 0 ,此時(shí)需要先排序,判斷 k 是否為奇數(shù),如果是奇數(shù)直接對(duì)最小位進(jìn)行取反 最終遍歷數(shù)組求和 ? K 次取反后最

    2024年04月27日
    瀏覽(96)
  • 【Leetcode60天帶刷】day33回溯算法——1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果

    【Leetcode60天帶刷】day33回溯算法——1005.K次取反后最大化的數(shù)組和 134. 加油站 135. 分發(fā)糖果

    ? 1005. K 次取反后最大化的數(shù)組和 給你一個(gè)整數(shù)數(shù)組? nums ?和一個(gè)整數(shù)? k ?,按以下方法修改該數(shù)組: 選擇某個(gè)下標(biāo)? i ?并將? nums[i] ?替換為? -nums[i] ?。 重復(fù)這個(gè)過程恰好? k ?次??梢远啻芜x擇同一個(gè)下標(biāo)? i ?。 以這種方式修改數(shù)組后,返回?cái)?shù)組? 可能的最大和 ?。

    2024年02月11日
    瀏覽(22)
  • 力扣算法刷題Day34|貪心:K次取反后最大化的數(shù)組和 加油站 分發(fā)糖果

    力扣題目:# 1005.K次取反后最大化的數(shù)組和? 刷題時(shí)長(zhǎng):10min 解題方法:貪心 復(fù)雜度分析 時(shí)間O(n) 空間O(1) 問題總結(jié) 無 本題收獲 貪心思路:兩次貪心 在包含正負(fù)無序的整數(shù)數(shù)組中,如何轉(zhuǎn)變K次正負(fù),讓數(shù)組和達(dá)到最大 局部最優(yōu):讓絕對(duì)值大的負(fù)數(shù)變?yōu)檎龜?shù),當(dāng)前數(shù)值達(dá)到

    2024年02月09日
    瀏覽(39)
  • LeetCode刷題筆記【25】:貪心算法專題-3(K次取反后最大化的數(shù)組和、加油站、分發(fā)糖果)

    LeetCode刷題筆記【25】:貪心算法專題-3(K次取反后最大化的數(shù)組和、加油站、分發(fā)糖果)

    參考前文 參考文章: LeetCode刷題筆記【23】:貪心算法專題-1(分發(fā)餅干、擺動(dòng)序列、最大子序和) LeetCode刷題筆記【24】:貪心算法專題-2(買賣股票的最佳時(shí)機(jī)II、跳躍游戲、跳躍游戲II) LeetCode鏈接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 首先 sor

    2024年02月09日
    瀏覽(93)
  • C++力扣題目1005--K次取反后最大化的數(shù)組和 134--加油站 135--分發(fā)糖果

    C++力扣題目1005--K次取反后最大化的數(shù)組和 134--加油站 135--分發(fā)糖果

    力扣題目鏈接(opens new window) 給定一個(gè)整數(shù)數(shù)組 A,我們只能用以下方法修改該數(shù)組:我們選擇某個(gè)索引 i?并將 A[i] 替換為 -A[i],然后總共重復(fù)這個(gè)過程 K 次。(我們可以多次選擇同一個(gè)索引 i。) 以這種方式修改數(shù)組后,返回?cái)?shù)組可能的最大和。 示例 1: 輸入:A = [4,2,3],

    2024年01月21日
    瀏覽(23)
  • 【隨想錄】Day35—第八章 貪心算法 part04

    【隨想錄】Day35—第八章 貪心算法 part04

    題目鏈接:435. 無重疊區(qū)間 貪心思路 : 正向遍歷數(shù)組,利用哈希表存儲(chǔ)三個(gè)面額的錢的個(gè)數(shù) ? 檸檬水找零 ——題解思路 題目鏈接:406. 根據(jù)身高重建隊(duì)列 貪心思路 : 1. 身高降序排 :先根據(jù)身高進(jìn)行降序排序,若身高相同,則 根據(jù) 前面有多少人升序排。 2. 按照排序位置

    2024年04月27日
    瀏覽(95)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包,優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包