1005.K次取反后最大化的數(shù)組和
力扣題目鏈接(opens new window)
給定一個(gè)整數(shù)數(shù)組 A，我們只能用以下方法修改該數(shù)組：我們選擇某個(gè)索引 i?并將 A[i] 替換為 -A[i]，然后總共重復(fù)這個(gè)過(guò)程 K 次。（我們可以多次選擇同一個(gè)索引 i。）
以這種方式修改數(shù)組后，返回?cái)?shù)組可能的最大和。
示例 1：
- 輸入：A = [4,2,3], K = 1
- 輸出：5
- 解釋：選擇索引 (1,) ，然后 A 變?yōu)?[4,-2,3]。
示例 2：
- 輸入：A = [3,-1,0,2], K = 3
- 輸出：6
- 解釋：選擇索引 (1, 2, 2) ，然后 A 變?yōu)?[3,1,0,2]。
示例 3：
- 輸入：A = [2,-3,-1,5,-4], K = 2
- 輸出：13
- 解釋：選擇索引 (1, 4) ，然后 A 變?yōu)?[2,3,-1,5,4]。
提示：
- 1 <= A.length <= 10000
- 1 <= K <= 10000
- -100 <= A[i] <= 100
#思路
本題思路其實(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í)的問(wèn)題是一個(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)出來(lái) 經(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)單起來(lái)，會(huì)讓人簡(jiǎn)單到開(kāi)始懷疑：本來(lái)不就應(yīng)該這么做么？這也算是算法？我認(rèn)為這不是貪心？
本題其實(shí)很簡(jiǎn)單，不會(huì)貪心算法的同學(xué)都可以做出來(lái)，但是我還是全程用貪心的思路來(lái)講解。
因?yàn)樨澬牡乃伎挤绞揭欢ㄒ校?/p>
如果沒(méi)有貪心的思考方式（局部最優(yōu)，全局最優(yōu)），很容易陷入貪心簡(jiǎn)單題憑感覺(jué)做，貪心難題直接不會(huì)做，其實(shí)這樣就鍛煉不了貪心的思考方式了。
所以明知道是貪心簡(jiǎn)單題，也要靠貪心的思考方式來(lái)解題，這樣對(duì)培養(yǎng)解題感覺(jué)很有幫助。
?
134. 加油站
力扣題目鏈接(opens new window)
在一條環(huán)路上有?N?個(gè)加油站，其中第?i?個(gè)加油站有汽油?gas[i]?升。
你有一輛油箱容量無(wú)限的的汽車，從第 i 個(gè)加油站開(kāi)往第 i+1?個(gè)加油站需要消耗汽油?cost[i]?升。你從其中的一個(gè)加油站出發(fā)，開(kāi)始時(shí)油箱為空。
如果你可以繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)，否則返回 -1。
說(shuō)明:
- 如果題目有解，該答案即為唯一答案。
- 輸入數(shù)組均為非空數(shù)組，且長(zhǎng)度相同。
- 輸入數(shù)組中的元素均為非負(fù)數(shù)。
示例?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)路行駛一周。
#思路
#暴力方法
暴力的方法很明顯就是O(n^2)的，遍歷每一個(gè)加油站為起點(diǎn)的情況，模擬一圈。
如果跑了一圈，中途沒(méi)有斷油，而且最后油量大于等于0，說(shuō)明這個(gè)起點(diǎn)是ok的。
暴力的方法思路比較簡(jiǎn)單，但代碼寫起來(lái)也不是很容易，關(guān)鍵是要模擬跑一圈的過(guò)程。
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;
}
};
- 時(shí)間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(1)
#貪心算法（方法一）
直接從全局進(jìn)行貪心選擇，情況如下：
-
情況一：如果gas的總和小于cost總和，那么無(wú)論從哪里出發(fā)，一定是跑不了一圈的
-
情況二：rest[i] = gas[i]-cost[i]為一天剩下的油，i從0開(kāi)始計(jì)算累加到最后一站，如果累加沒(méi)有出現(xiàn)負(fù)數(shù)，說(shuō)明從0出發(fā)，油就沒(méi)有斷過(guò)，那么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;
}
};
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
其實(shí)我不認(rèn)為這種方式是貪心算法，因?yàn)闆](méi)有找出局部最優(yōu)，而是直接從全局最優(yōu)的角度上思考問(wèn)題。
但這種解法又說(shuō)不出是什么方法，這就是一個(gè)從全局角度選取最優(yōu)解的模擬操作。
所以對(duì)于本解法是貪心，我持保留意見(jiàn)！
但不管怎么說(shuō)，解法畢竟還是巧妙的，不用過(guò)于執(zhí)著于其名字稱呼。
#貪心算法（方法二）
可以換一個(gè)思路，首先如果總油量減去總消耗大于等于零那么一定可以跑完一圈，說(shuō)明 各個(gè)站點(diǎn)的加油站 剩油量rest[i]相加一定是大于等于零的。
每個(gè)加油站的剩余量rest[i]為gas[i] - cost[i]。
i從0開(kāi)始累加rest[i]，和記為curSum，一旦curSum小于零，說(shuō)明[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了。
那有沒(méi)有可能 [0，i] 區(qū)間 選某一個(gè)作為起點(diǎn)，累加到 i這里 curSum是不會(huì)小于零呢？ 如圖：
如果 curSum<0 說(shuō)明 區(qū)間和1 + 區(qū)間和2 < 0， 那么 假設(shè)從上圖中的位置開(kāi)始計(jì)數(shù)curSum不會(huì)小于0的話，就是 區(qū)間和2>0。
區(qū)間和1 + 區(qū)間和2 < 0 同時(shí) 區(qū)間和2>0，只能說(shuō)明區(qū)間和1 < 0， 那么就會(huì)從假設(shè)的箭頭初就開(kāi)始從新選擇其實(shí)位置了。
那么局部最優(yōu)：當(dāng)前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因?yàn)閺膇之前開(kāi)始一定不行。全局最優(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開(kāi)始
}
}
if (totalSum < 0) return -1; // 說(shuō)明怎么走都不可能跑一圈了
return start;
}
};
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
說(shuō)這種解法為貪心算法，才是有理有據(jù)的，因?yàn)槿肿顑?yōu)解是根據(jù)局部最優(yōu)推導(dǎo)出來(lái)的。
#總結(jié)
對(duì)于本題首先給出了暴力解法，暴力解法模擬跑一圈的過(guò)程其實(shí)比較考驗(yàn)代碼技巧的，要對(duì)while使用的很熟練。
然后給出了兩種貪心算法，對(duì)于第一種貪心方法，其實(shí)我認(rèn)為就是一種直接從全局選取最優(yōu)的模擬操作，思路還是很巧妙的，值得學(xué)習(xí)一下。
對(duì)于第二種貪心方法，才真正體現(xiàn)出貪心的精髓，用局部最優(yōu)可以推出全局最優(yōu)，進(jìn)而求得起始位置。
?
135. 分發(fā)糖果
力扣題目鏈接(opens new window)
老師想給孩子們分發(fā)糖果，有 N?個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們?cè)u(píng)分。
你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：
- 每個(gè)孩子至少分配到 1 個(gè)糖果。
- 相鄰的孩子中，評(píng)分高的孩子必須獲得更多的糖果。
那么這樣下來(lái)，老師至少需要準(zhǔn)備多少顆糖果呢？
示例?1:
- 輸入: [1,0,2]
- 輸出: 5
- 解釋: 你可以分別給這三個(gè)孩子分發(fā) 2、1、2 顆糖果。
示例?2:
- 輸入: [1,2,2]
- 輸出: 4
- 解釋: 你可以分別給這三個(gè)孩子分發(fā) 1、2、1 顆糖果。第三個(gè)孩子只得到 1 顆糖果，這已滿足上述兩個(gè)條件。
#思路
這道題目一定是要確定一邊之后，再確定另一邊，例如比較每一個(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ì)有疑問(wèn)，為什么不能從前向后遍歷呢？
因?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]的糖果多。
如圖：
所以該過(guò)程代碼如下：
// 從后向前
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ì)顧此失彼。
那么本題我采用了兩次貪心的策略：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-813015.html
- 一次是從左到右遍歷，只比較右邊孩子評(píng)分比左邊大的情況。
- 一次是從右到左遍歷，只比較左邊孩子評(píng)分比右邊大的情況。
這樣從局部最優(yōu)推出了全局最優(yōu)，即：相鄰的孩子中，評(píng)分高的孩子獲得更多的糖果。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-813015.html
到了這里，關(guān)于C++力扣題目1005--K次取反后最大化的數(shù)組和 134--加油站 135--分發(fā)糖果的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
