LeetCode 1005 K次組飯后最大化的數組

這題貪的主要是數值最大化。如果K > 負數個數，我們就先將負數全部轉換成它的相反數，并將K--，之后K剩余的值可以對2取模，為0的話直接得出最后結果，為的話我們要在當前所有值里取最小值，對其進行取反。如果K <= 負數個數，K用完直接結束，將數組累加即可。

代碼如下：

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int sum = 0;for (int i = 0; i < nums.length; i++) {if (k == 0) break;if (nums[i] < 0) {k--;nums[i] *= -1;} else break;}if (k > 0 && k % 2 == 1) {Arrays.sort(nums);nums[0] *= -1;}for (int i = 0; i < nums.length; i++) {sum += nums[i];}return sum;}
}

LeetCode 134 加油站

兄弟們，這題我老一時隔一天，終于寫出來了！其實也不是很難，就是一個比較復雜的模擬。但是里面用貪心縮短了循環次數，這就造成我們的麻煩了。

主要思路是用一個cnt模擬每次的起點，在循環內部用一個i變量模擬走過的加油站數，這里面涉及到i到達右邊界后要回到1的問題。比較麻煩的是在剛開始起步時需要先走一步，便于二重循環的判斷條件能夠正常運轉，不然i和cnt開始時處于同一位置無法判斷是已經走一圈了還是剛開始的狀態，這個后面需要優化下不然面試時也無法立刻就寫出來。

同時這里面還用到一個特別的規律：如果從某個加油站起步沒能到達的第一個加油站是a，那么從該起始加油站到a中間的任何一個加油站，都無法到達a，所以遇到無法到達的第一個加油站時，直接將cnt移到i + 1退出循環即可。需要注意判別cnt比i+1大的情況，這是為了防止多次遍歷造成死循環的出現。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int cnt = 0;int gasNum = 0;while (cnt < gas.length) {gasNum += (gas[cnt] - cost[cnt]);if (gasNum < 0)  {cnt = cnt + 1;gasNum = 0;continue;}int i = cnt + 1;if (i == gas.length) i = 0;while (i != cnt) {if (gasNum + gas[i] - cost[i] >= 0) {gasNum += (gas[i] - cost[i]);i++;} else if (cnt < i + 1) {gasNum = 0;cnt = i + 1;break;} else {cnt = gas.length;break;}if (i == gas.length) i = 0;}if (i == cnt) return cnt;}   return -1;}
}

LeetCode 135 分發糖果

這題要貪心兩次，一次從前往后遍歷，如果右孩子比左孩子大并且他的評分比左孩子小或者相等，那么他的評分賦為左孩子評分+1

第二次從后往前遍歷，如果左孩子比右孩子大并且他的評分比右孩子小或者相等，那么他的評分等于右孩子評分+1

兩次分別取反向遍歷的原因是有遞推關系存在，前序遍歷可以處理這樣的情況：假如左邊增加了，右邊也要跟著增長，適用于右邊大于左邊的情況；后序遍歷可以處理這樣的情況：假如右邊增長了，左邊也要跟著增長，適用于左邊大于右邊的情況

這題需要再看下，不知道解法恐怕挺難寫得出來

代碼如下：

class Solution {public int candy(int[] ratings) {int[] num = new int[ratings.length];for (int i = 0; i < num.length; i++) {num[i] = 1;}for (int i = 0; i < ratings.length - 1; i++) {if (ratings[i] < ratings[i + 1] && num[i + 1] <= num[i]) num[i + 1] = num[i] + 1;}for (int i = ratings.length - 1; i > 0; i--) {if (ratings[i - 1] > ratings[i] && num[i - 1] <= num[i]) num[i - 1] = num[i] + 1;}int sum = 0;for (int i = 0; i < num.length; i++) sum+= num[i];return sum;}
}