Leetcode 1005.K 次取反后最大化的数组和

题目：1005.K 次取反后最大化的数组和

初始思路

优先把负数变成正数，如果都是正数的话争取翻转两次变回原来的数，如果是单数的话就翻正数里最小的。

代码

  1. var largestSumAfterKNegations = function (nums, k) {
  2.     // 按照绝对值从大到小排序
  3.     nums.sort((a, b) => {
  4.         return Math.abs(b) - Math.abs(a)
  5.     })
  6.     for (let i = 0; i < nums.length; i++){
  7.         // 如果遇到负数，并且还有步骤，就反转
  8.         if (nums[i] < 0 && k > 0) {
  9.             nums[i] *= -1
  10.             k--
  11.         }
  12.     }
  13.     // 如果还剩奇数次步骤，反复翻转最小的元素，将k用完
  14.     // 如果剩偶数次的话，可以当没有操作过，直接跳过
  15.     if (k > 0 && k % 2 === 1) {
  16.         nums[nums.length - 1] *= -1
  17.     }
  18.     k = 0
  19.     // reduce方法求和
  20.     return nums.reduce((sum, curVal) => {
  21.         return sum + curVal
  22.     }, 0)
  23. };

感想

  1. 局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
  2. 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
  3. 第二步：从前向后遍历，遇到负数将其变为正数，同时K—
  4. 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
  5. 第四步：求和

Leetcode 134.加油站

题目：134.加油站

初始思路

如果汽油总和小于花费的话，无论如何出发都到不了。

代码

  1. var canCompleteCircuit = function (gas, cost) {
  2.     const len = gas.length
  3.     let start = 0
  4.     let curSum = 0
  5.     let totalSum = 0
  6.     for (let i = 0; i < len; i++){
  7.         curSum += gas[i] - cost[i]
  8.         totalSum += gas[i] - cost[i]
  9.         // 如果在中途断油了
  10.         if (curSum < 0) {
  11.             // curSum从0开始
  12.             curSum = 0
  13.             // 起始位置更新为 i+1
  14.             start = i + 1
  15.         }
  16.     }
  17.     // 如果gas总和小于cost总和，说明怎样都走不到
  18.     if (totalSum < 0) return -1
  19.     return start
  20. };

感想

  1. 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。
  2. 从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

Leetcode 135.分发糖果

题目：135.分发糖果

初始思路

多给糖果会破产是吧

代码

  1. var candy = function (ratings) {
  2.     let candys = new Array(ratings.length).fill(1)
  3.     // 第一遍遍历：从左到右遍历，如果右边的评分大于左边就加一
  4.     for (let i = 1; i < ratings.length; i++){
  5.         if (ratings[i] > ratings[i - 1]) {
  6.             candys[i] = candys[i - 1] + 1
  7.         }
  8.     }
  9.     // 第二遍遍历：从右到左遍历，如果左边的评分大于右边的评分就处理贪心
  10.     for (let i = ratings.length - 2; i >= 0; i--){
  11.         // 左边的糖果应该取本身的糖果数（符合比它左边大）和右边糖果数 + 1二者的最大值，这样才符合 它比它左边的大，也比它右边大
  12.         if (ratings[i] > ratings[i + 1]) {
  13.             candys[i] = Math.max(candys[i], candys[i + 1] + 1)
  14.         }
  15.     }
  16.     let count = candys.reduce((sum, curVal) => {
  17.         return sum + curVal
  18.     }, 0)
  19.     return count
  20. };

感想

  1. 先确定右边大于左边（从前往后遍历）：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
  2. 再确定左边大于右边（从后往前遍历）：左边的糖果应该取本身的糖果数（符合比它左边大）和右边糖果数 + 1二者的最大值，这样才符合 它比它左边的大，也比它右边大
  3. 解法很精妙