DAY34：贪心算法part、1005134135

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

基本思路

这道题的思路比较简单，如果有负数，就先把最大的负数转化成正数，如果全部转换完之后还有k剩余，就将最小的正数反复正负变化。但是需要注意一点代码的写法。

代码注意点

• 定义绝对值从大到小的排序写法
• 判断k--条件的时候需要加上k>0
• k剩余的时候最小的正数反复变化的代码，不需要用循环，直接求余数判断就可以。不然会超出时间限制。

  时间复杂度: O(nlogn)

  空间复杂度: O(1)

  class Solution {
  static bool cmp(int a, int b) {
      return abs(a) > abs(b);
  }
  public:
      int largestSumAfterKNegations(vector& nums, int k) {
          sort(nums.begin(), nums.end(), cmp);
          for(int i = 0; i < nums.size(); i++){
              if(nums[i] <= 0 && k > 0){
                  k--;
                  nums[i] = -nums[i];
              }
          }
          if (k % 2 == 1) nums[nums.size() - 1] *= -1;
          int result = 0;
          for(int i = 0; i < nums.size(); i++){
              result += nums[i];
          }
          
          return result;
      }
  };

  Leetcode: 134 加油站

  首先能想到的时候，如果消耗的油量比汽油量大，那肯定是没办法开到的。如果小于的话，肯定有办法开到，但是对于起点就需要讲究了。

  因此思路是每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

  时间复杂度：O(n)

  空间复杂度：O(1)

  class Solution {
  public:
      int canCompleteCircuit(vector& gas, vector& cost) {
          int totalgas = 0;
          int totalcost = 0;
          for(int i = 0; i < gas.size();i++) totalgas += gas[i];
          for(int i = 0; i < cost.size();i++) totalcost += cost[i];
          if(totalcost > totalgas) return -1;
          int currest = 0;
          int start = 0;
          for(int i = 0; i < gas.size(); i++){
              currest += gas[i] - cost[i];
              if(currest < 0) {
                  start = i + 1;//更新起始位置
                  currest = 0;//更新剩余油量
              }
          }
          return start;
      }
  };

  Leetcode: 135 分发糖果

  这题乍一看题目都没有理解是啥意思，只能学习一下题解

  代码随想录

  采用了两次贪心的策略：

  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

    在先确定右边评分比左边评分大的情况下，从前向后遍历的过程中candy[i] = candy[i-1]+1是一种代码的写法

    在确定左边评分比右边评分大的情况下，从后向前的过程中，cand[i] = max(candy[i], cand[i+1] +1);

    时间复杂度O(N)

    空间复杂度O(N)

    class Solution {
    public:
        int candy(vector& ratings) {
            vector candy(ratings.size(), 1);
            for(int i = 1; i < candy.size() ; i++){
                if(ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
            }
            for(int i = candy.size() - 2; i >= 0; i--){
                if(ratings[i] > ratings[i + 1]) candy[i] = max(candy[i], candy[i + 1] + 1);
            }
            int result = 0;
            for(int i = 0; i < candy.size(); i++){
                result += candy[i];
            }
            return result;
        }
    };