day34 1005

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

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {

        Arrays.sort(nums);
        int i=0;
        while(k>0&&i<nums.length&&nums[i]<0){     //先把负数给处理掉 (左边的负数 绝对值肯定最大  所以左边开始处理)
            nums[i]=-nums[i];
            i++;
            k--;
        }
        //此时判断  k的次数  如果 k==0 说明已经是最优解了  直接求和
        if(k==0) return Arrays.stream(nums).sum();

        //如果k>0  说明 负数的情况已经处理完  ，那么要达到最大和，只能把k用在最小的正数上
        //此时  只能对 最小正数操作 ，如果k为偶数那和就不用边，如果是奇数，那就动最小的
        Arrays.sort(nums);  //重新排序一下 全是>=0 的数
        if(k%2==1&&nums[0]!=0){   //特殊情况 如果为0 那就不用变
            nums[0]=-nums[0];
        }
        return Arrays.stream(nums).sum();  
    }
}

134. 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //先判断入是不是大于出，如果小，不用继续了
        if(Arrays.stream(gas).sum()-Arrays.stream(cost).sum()<0) return -1;/

        int start=0;
        int sum=0;
        for(int i=0;i<gas.length;i++){//因为是环（而且前提条件已经通过），不满足条件的end+1开始必是满足条件的
            sum=sum+gas[i]-cost[i];

            if(sum<0){
                start=i+1;
                sum=0;
            }
        }
        return start;


    }
}

原文地址：http://www.cnblogs.com/wdnmdp/p/16823057.html