第八章?貪心算法?part03

• ?1005.K次取反后最大化的數(shù)組和?

  class Solution {public int largestSumAfterKNegations(int[] nums, int K) {// 將數(shù)組按照絕對值大小從大到小排序，注意要按照絕對值的大小nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len = nums.length;	    for (int i = 0; i < len; i++) {//從前向后遍歷，遇到負數(shù)將其變?yōu)檎龜?shù)，同時K--if (nums[i] < 0 && K > 0) {nums[i] = -nums[i];K--;}}// 如果K還大于0，那么反復轉變數(shù)值最小的元素，將K用完if (K % 2 == 1) nums[len - 1] = -nums[len - 1];return Arrays.stream(nums).sum();}
  }

  思路：讓絕對值最大的負數(shù)變?yōu)檎龜?shù)，如果負數(shù)都變?yōu)檎龜?shù)了，k還大于0，就把最小的正數(shù)反復×負號。

• ?134.?加油站

  // 解法2
  class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {index = (i + 1) % gas.length ; curSum = 0;}}if (totalSum < 0) return -1;return index;}
  }

  思路：把每個點的存儲或消耗的油量算出來，如果從一個點走到另一個點curSum<0，那么就從i+1出發(fā)，只要totalSum>0，總有一個點可以當出發(fā)點。

• ?135.?分發(fā)糖果??

  class Solution {/**分兩個階段1、起點下標1 從左往右，只要 右邊 比 左邊 大，右邊的糖果=左邊 + 12、起點下標 ratings.length - 2 從右往左， 只要左邊 比 右邊 大，此時 左邊的糖果應該 取本身的糖果數(shù)（符合比它左邊大） 和 右邊糖果數(shù) + 1 二者的最大值，這樣才符合 它比它左邊的大，也比它右邊大*/public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;for (int i = 1; i < len; i++) {candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;}for (int i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);}}int ans = 0;for (int num : candyVec) {ans += num;}return ans;}
  }

  思路：要把左右孩子分開比較，一起比較容易顧此失彼，而且！！要先從前往后，再從后往前，把最近更新的都利用上，從后往前更新時，要將原糖果數(shù)和candy[i+1]+1相比較，取滿足條件的最大值。