0.引言
● 1005.K次取反后最大化的數組和
● 134. 加油站
● 135. 分發(fā)糖果
1005.# K 次取反后最大化的數組和
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (51.17%) | 344 | - |
給你一個整數數組 nums 和一個整數 k ，按以下方法修改該數組：
- 選擇某個下標
i并將nums[i]替換為-nums[i]。
重復這個過程恰好 k 次?？梢远啻芜x擇同一個下標 i 。
以這種方式修改數組后，返回數組 可能的最大和 。
示例 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 <= 10<sup>4</sup>-100 <= nums[i] <= 1001 <= k <= 10<sup>4</sup>
貪心思想
自己嘗試：
/*
* @lc app=leetcode.cn id=1005 lang=cpp
*
* [1005] K 次取反后最大化的數組和
*/
// @lc code=start
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() && k > 0; ++i) {
std::cout << i << ", ";
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
} else if (nums[i] == 0) {
k--;
i--;
} else {
nums[i] = -nums[i];
k--;
i--;
}
}
return std::accumulate(nums.begin(), nums.end(), 0);
}
};
// @lc code=end
有case過不了：
更正：
/*
* @lc app=leetcode.cn id=1005 lang=cpp
*
* [1005] K 次取反后最大化的數組和
*/
// @lc code=start
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
// 分兩步驟，先把有負數的情況處理了
for (int i = 0; i < nums.size() && k > 0; ++i) {
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
}
}
// 然后再按照最小的一位進行反轉
if (k % 2 == 1) {
int min_value = *min_element(nums.begin(), nums.end());
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum - 2 * min_value;
}
return std::accumulate(nums.begin(), nums.end(), 0);
}
};
// @lc code=end
134. # 加油站
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (52.22%) | 1203 | - |
在一條環(huán)路上有 n 個加油站，其中第 i 個加油站有汽油 gas[i]升。
你有一輛油箱容量無限的的汽車，從第i個加油站開往第i+1個加油站需要消耗汽油 cost[i]升。你從其中的一個加油站出發(fā)，開始時油箱為空。
給定兩個整數數組 gas 和 cost ，如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。
示例 1:
輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號加油站。
因此，3 可為起始索引。
示例 2:
輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號或 1 號加油站出發(fā)，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發(fā)，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環(huán)路行駛一周。
提示:
gas.length == ncost.length == n1 <= n <= 10<sup>5</sup>0 <= gas[i], cost[i] <= 10<sup>4</sup>
貪心思想
自己嘗試，好像找起點的方法不對：
/*
* @lc app=leetcode.cn id=134 lang=cpp
*
* [134] 加油站
*/
// @lc code=start
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = find_start(gas, cost);
if (start < 0) return -1;
int remain = gas[start];
for (int i = start + 1; i < gas.size(); ++i) {
remain = remain + gas[i] - cost[i - 1];
if (remain < 0) return -1;
}
// 0 特殊處理
remain = remain - gas[0] - cost[cost.size() - 1];
for (int i = 1; i <= start; ++i) {
remain = remain + gas[i] - cost[i];
if (remain < 0) return -1;
}
return start;
}
private:
int find_start(std::vector<int>& gas, std::vector<int>& cost) {
int i = 0;
int size = gas.size() < cost.size() ? gas.size() : cost.size();
while (size--) {
if (gas[i] > cost[i]) {
return i;
}
i++;
}
return -1;
}
};
// @lc code=end
可以換一個思路，首先如果總油量減去總消耗大于等于零那么一定可以跑完一圈，說明 各個站點的加油站 剩油量rest[i]相加一定是大于等于零的。
每個加油站的剩余量rest[i]為gas[i] - cost[i]。
i從0開始累加rest[i]，和記為curSum，一旦curSum小于零，說明[0, i]區(qū)間都不能作為起始位置，因為這個區(qū)間選擇任何一個位置作為起點，到i這里都會斷油，那么起始位置從i+1算起，再從0計算curSum。
如圖：
那么為什么一旦[0，i] 區(qū)間和為負數，起始位置就可以是i+1呢，i+1后面就不會出現更大的負數？
如果出現更大的負數，就是更新i，那么起始位置又變成新的i+1了。
那有沒有可能 [0，i] 區(qū)間 選某一個作為起點，累加到 i這里 curSum是不會小于零呢？ 如圖：
如果 curSum<0 說明 區(qū)間和1 + 區(qū)間和2 < 0， 那么 假設從上圖中的位置開始計數curSum不會小于0的話，就是 區(qū)間和2>0。
區(qū)間和1 + 區(qū)間和2 < 0 同時 區(qū)間和2>0，只能說明區(qū)間和1 < 0， 那么就會從假設的箭頭初就開始從新選擇其實位置了。
那么局部最優(yōu)：當前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因為從i之前開始一定不行。全局最優(yōu)：找到可以跑一圈的起始位置。
局部最優(yōu)可以推出全局最優(yōu)，找不出反例，試試貪心！
/*
* @lc app=leetcode.cn id=134 lang=cpp
*
* [134] 加油站
*/
// @lc code=start
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = 0, total_gas = 0, total_cost = 0, curr_gas = 0;
// 能否循環(huán)看總的油量即可
// 問題就轉換為找start
for (int i = 0; i < gas.size(); ++i) {
total_gas += gas[i];
total_cost += cost[i];
curr_gas += gas[i] - cost[i];
if (curr_gas < 0) {
start = i + 1;
curr_gas = 0;
}
}
if (total_gas >= total_cost) {
return start;
} else {
return -1;
}
}
};
// @lc code=end
135. # 分發(fā)糖果
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Hard (49.56%) | 1160 | - |
n 個孩子站成一排。給你一個整數數組 ratings 表示每個孩子的評分。
你需要按照以下要求，給這些孩子分發(fā)糖果：
- 每個孩子至少分配到
1個糖果。 - 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發(fā)糖果，計算并返回需要準備的 最少糖果數目 。
示例 1：
輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個、第二個、第三個孩子分發(fā) 2、1、2 顆糖果。
示例 2：
輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個、第二個、第三個孩子分發(fā) 1、2、1 顆糖果。
第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件。
提示：
n == ratings.length1 <= n <= 2 * 10<sup>4</sup>0 <= ratings[i] <= 2 * 10<sup>4</sup>
貪心思想
這道題目一定是要確定一邊之后，再確定另一邊，例如比較每一個孩子的左邊，然后再比較右邊，如果兩邊一起考慮一定會顧此失彼。
先確定右邊評分大于左邊的情況（也就是從前向后遍歷）
此時局部最優(yōu)：只要右邊評分比左邊大，右邊的孩子就多一個糖果，全局最優(yōu)：相鄰的孩子中，評分高的右孩子獲得比左邊孩子更多的糖果
局部最優(yōu)可以推出全局最優(yōu)。
/*
* @lc app=leetcode.cn id=135 lang=cpp
*
* [135] 分發(fā)糖果
*/
// @lc code=start
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
// 從左到右遍歷
for (int i = 1; i < n; ++i) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 從右到左遍歷
for (int i = n - 2; i >= 0; --i) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
int total_candies = 0;
for (int candy : candies) {
total_candies += candy;
}
return total_candies;
}
};
// @lc code=end
4.簡書什么玩意兒？？
