非科班學習算法day29 | LeetCode134:加油站 ，Leetcode135:分發糖果 ，Leetcode860:檸檬水找零?

---

介紹

包含LC的兩道題目，還有相應概念的補充。

相關圖解和更多版本：

代碼隨想錄 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

---

??

一、LeetCode題目

1.LeetCode134:加油站?

題目鏈接：134. 加油站 - 力扣（LeetCode）

題目解析

? ? ? ?這里很容易被示例的做法干擾，實際上，我們需要的就是別對兩個數組，到達一個位置(i)對應的需要加上gas(i)減去cost(i)，這就我們需要比對的。這里先說一種之前有局限性的思路，先對兩個數組相減，構造新的數組，如果數組元素為負數表示到達不了下一位，那么繼續遍歷，找到第一個不為負數的位置為初始位置，并且控制總和為負數的話返回-1,這樣的做法最大的問題就在于我沒有意識到，加油的過程也是需要一個初始量累計的，所以我不能單純比較一個位置為負數就跳過這個位置，而應該是用cur變量維護start的位置，如果cur在累加的過程中變為負數，那么就重置cur并且將返回的start向后加一位。

?c++代碼如下：

class Solution {
public://gas是加的，cost是減的//建立差值數組，如果數組和是負數，那么不可能有解，如果大于等于則有唯一解int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int tolsum = 0;int cursum = 0;int start = 0;vector<int> nd = vector<int>(gas.size(),0);for(int i = 0; i<gas.size();i++){nd[i] = gas[i] - cost[i];tolsum+=nd[i];cursum+=nd[i];if(cursum<0){start = i+1;cursum = 0;}}if(tolsum<0) return -1;return start;}
};

注意點1：這里可能會疑惑start超出最后一位怎么辦，實際上，當cur超出最后一位的時候，并沒有影響，不會訪問空指針；而且關于最后的返回有tolsum控制，如果start超出，直接就返回-1了。注意！這里整個循環已經完成了一輪遍歷，只不過遍歷是從頭到尾的。

?2.Leetcode135:分發糖果?

題目鏈接：135. 分發糖果 - 力扣（LeetCode）

題目解析

? ? ? ?第一次做就是中了圈套，總想一次就確定好糖果的數量，這就導致條件特別多，很容易混亂，這里就使用了一種非常常用的方法，兩個方向分別遍歷，去比較一個元素的左邊和右邊元素的關系，同時維護糖果數組，這樣就可以實時更正。

? ? ? ? 這里有一個問題就是為什么需要兩個方向，因為在比較右邊元素的時候，和左邊一樣，有一個累計的過程，如果從左邊遍歷比較右邊的元素，就沒法實時更新下一個元素的信息。

?C++代碼如下：?

class Solution {
public:// 不能顧此失彼，分為兩邊去比對孩子int candy(vector<int>& ratings) {// 創建需要維護的糖果數組vector<int> candys = vector<int>(ratings.size(), 1);// 想象排隊過程，先和左邊的孩子比是大是小for (int i = 1; i < ratings.size(); ++i) {// 維護數組// 左邊小-加糖果if (ratings[i] > ratings[i - 1]) {candys[i] = candys[i - 1] + 1;}// 左邊大-重置糖果else {candys[i] = 1;}}// 比對右邊孩子是大是小for (int i = ratings.size() - 2; i >= 0; --i) {// 在之前的基礎上維護數組// 右邊小-加糖果if (ratings[i + 1] < ratings[i]) {candys[i] = max(candys[i], candys[i + 1] + 1);}// 右邊大-無需操作}// 累計糖果int sum = 0;for (int i = 0; i < candys.size(); ++i) {sum += candys[i];}return sum;}
};

注意點1：這里初始化，將糖果數組全部初始化為1，因為題目要求孩子的最少糖果數是1。所以在左邊遍歷的過程中，遇到需要重置的糖果，也可以不寫這個命令，因為已經做好了初始化。

注意點2：第二遍為什么右邊大不需要維護數組，可以舉一個數組作為例子，當前其實也是重置了糖果數量為1，但是要和之前的糖果數取一個大值，那么不就是當前的糖果數么，所以不需要處理。?

3.Leetcode860:檸檬水找零

題目鏈接：860. 檸檬水找零 - 力扣（LeetCode）

題目解析

? ? ? ?終于在貪心遇到一道爽題，這道題其實也就是模擬生活中找零的行為，但是需要注意的就是可能找不開零！那么我們的貪心策略就是盡可能找大的零（10）把靈活的5留著去找10的零，或者沒有10的時候去找20的零。策略有了，就需要變量維護當前的錢的數量，這里沒有維護20，因為20并不用于找零，只是作為判斷條件來做找零行為。

C++代碼如下：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int m5 = 0;int m10 = 0;for (int i = 0; i < bills.size(); ++i) {if (bills[i] == 5)m5++;if (bills[i] == 10) {m10++;m5--;}if (bills[i] == 20) {if (m10 == 0) {m5 -= 3;} else {m10--;m5--;}}if (m5 < 0)return false;}return true;}
};

總結

打卡第29天，堅持！！！