本文章代碼以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ù)組 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 升汽油 開往 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。
代碼解析:
-
外層循環(huán):
for (int i = 0; i < cost.size(); i++)
?- 遍歷所有加油站,考慮每一個(gè)加油站作為起點(diǎn)。 -
int rest = gas[i] - cost[i];
?-?rest
?記錄從當(dāng)前加油站出發(fā)后的剩余油量。初始值是當(dāng)前加油站的油量減去開到下一個(gè)加油站所需的油量。 -
int index = (i + 1) % cost.size();
?- 初始化一個(gè)index
,它表示從第i個(gè)加油站出發(fā)后下一個(gè)要到達(dá)的加油站的位置。這里使用了取模操作,確保index
在數(shù)組的范圍內(nèi)。 -
內(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è)加油站。
-
-
判斷條件:
if (rest >= 0 && index == i)
?- 如果剩余油量不為負(fù)且回到了出發(fā)的加油站,則找到了一個(gè)滿足條件的起始位置。 -
如果所有的加油站都作為起點(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)形路線。
代碼解析:
-
初始化兩個(gè)變量:
-
curSum
:用于記錄從起點(diǎn)出發(fā),油箱里的油量累計(jì)值。 -
min
:用于記錄從起點(diǎn)出發(fā),油箱里的油量最小值。
-
-
第一個(gè)循環(huán):
for (int i = 0; i < gas.size(); i++)
?- 遍歷所有加油站,計(jì)算從起點(diǎn)出發(fā)到每個(gè)加油站的油量累計(jì)值,并更新curSum
和min
。 -
if (curSum < 0) return -1;
?- 如果curSum
為負(fù),說明油的總量不足以支撐整個(gè)環(huán)形路線,直接返回-1。 -
if (min >= 0) return 0;
?- 如果min
為非負(fù),說明從第0個(gè)加油站出發(fā),油箱里的油量始終為非負(fù),因此可以從第0個(gè)加油站出發(fā)完成整個(gè)環(huán)形路線。 -
第二個(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)。 -
在第二個(gè)循環(huán)中,每次都更新
min
的值,并檢查min
是否為非負(fù)。如果為非負(fù),說明從當(dāng)前加油站出發(fā)可以完成整個(gè)環(huán)形路線。 -
如果所有的加油站都嘗試過后都不滿足條件,返回-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。
如圖:
那么為什么一旦[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ì)小于零呢? 如圖:
如果 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;
}
如圖:
再確定左孩子大于右孩子的情況(從后向前遍歷)
遍歷順序這里有同學(xué)可能會(huì)有疑問,為什么不能從前向后遍歷呢?
因?yàn)?rating[5]與rating[4]的比較 要利用上 rating[5]與rating[6]的比較結(jié)果,所以 要從后向前遍歷。
如果從前向后遍歷,rating[5]與rating[4]的比較 就不能用上 rating[5]與rating[6]的比較結(jié)果了 。如圖:
所以確定左孩子大于右孩子的情況一定要從后向前遍歷!
如果 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]的糖果多。
如圖:
所以該過程代碼如下:
// 從后向前
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)分高的孩子獲得更多的糖果。文章來源:http://www.zghlxwxcb.cn/news/detail-679937.html
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)!