0.引言

● 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è)過(guò)程恰好 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 <= 10<sup>4</sup>
• -100 <= nums[i] <= 100
• 1 <= k <= 10<sup>4</sup>

Discussion | Solution

貪心思想

自己嘗試：

/*
 * @lc app=leetcode.cn id=1005 lang=cpp
 *
 * [1005] K 次取反后最大化的數(shù)組和
 */

// @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過(guò)不了：

image.png

更正：

/*
 * @lc app=leetcode.cn id=1005 lang=cpp
 *
 * [1005] K 次取反后最大化的數(shù)組和
 */

// @lc code=start
class Solution {
 public:
  int largestSumAfterKNegations(vector<int>& nums, int k) {
    std::sort(nums.begin(), nums.end());
    // 分兩步驟曹鸠，先把有負(fù)數(shù)的情況處理了
    for (int i = 0; i < nums.size() && k > 0; ++i) {
      if (nums[i] < 0) {
        nums[i] = -nums[i];
        k--;
      }
    }
    // 然后再按照最小的一位進(jìn)行反轉(zhuǎn)
    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. # 加油站

在一條環(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<sup>5</sup>
• 0 <= gas[i], cost[i] <= 10<sup>4</sup>

Discussion | Solution

貪心思想

image.png

自己嘗試洼哎，好像找起點(diǎn)的方法不對(duì)：

/*
 * @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

image.png

可以換一個(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切油。

如圖：

image.png

那么為什么一旦[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)甚牲，找不出反例义郑，試試貪心！

/*
 * @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)看總的油量即可
    // 問(wèn)題就轉(zhuǎ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ā)糖果

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 * 10<sup>4</sup>
• 0 <= ratings[i] <= 2 * 10<sup>4</sup>

Discussion | Solution

貪心思想

• 參考鏈接

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

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

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

• 局部最優(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.簡(jiǎn)書什么玩意兒澳窑？？

image.png