代码随想录刷题随记29-贪心3

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

leetcode链接
比较简单，首先对数组进行绝对值排序，然后如果是负数从小到大进行反转
如果是正数，就对一个绝对值最小的一直翻转
按照绝对值排序的实现可以通过重写比较器实现

class Solution {
    static  class Absulotecompare implements Comparator<Integer>{
        @Override
        public int compare(Integer a,Integer b){
         return Math.abs(b)-Math.abs(a);
        }
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        Integer []nums2=new Integer[nums.length];
        for( int i=0;i<nums.length;i++){
            nums2[i]=nums[i];
        }
        Arrays.sort(nums2,new Absulotecompare());
        int sum=0;
        //翻转
        int left=k;
        int index=0;
        for(int i=0;left>0&&i<nums.length;i++){
            if(nums2[i]>=0){
                continue;              
            }
            else{
              nums2[i]=-nums2[i];
              left--;  
            }            
        }
        while(left!=0){
            nums2[nums.length-1]=-nums2[nums.length-1];
            left--;
        }
        for(int i=0;i<nums.length;i++){
            sum+=nums2[i];
        }
        return sum;
    }
}

134. 加油站

leetcode链接
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。
在这里插入图片描述
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
          int [] tmp=new int[gas.length];
          for(int i=0;i<gas.length;i++){
            tmp[i]=gas[i]-cost[i];
          }
          int check=0;
          for( int i:tmp){
            check+=i;
          }
          if(check<0)
             return -1;
          int index=0;
          int sum=0;
          for(int i=0;i<gas.length;i++){
            sum+=tmp[i];
            if(sum<0){
                sum=0;
                index=i+1;
            }
          }
          return index;
    }
}

135. 分发糖果

leetcode链接
先确定右边评分大于左边的情况（也就是从前向后遍历）
在这里插入图片描述
再确定左孩子大于右孩子的情况（从后向前遍历）
为什么不能从前向后遍历呢？
因为 rating[5]与rating[4]的比较要利用上 rating[5]与rating[6]的比较结果

在这里插入图片描述
也就是说是要顺着一个顺序进行遍历的，要从小到大进行处理

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