Day30 第八章 贪心算法 part03

一. 学习文章及资料

二. 学习内容

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

(1) 贪心策略：

使用了两次贪心

局部最优：让绝对值大的负数变为正数，当前数值达到最大
全局最优：整个数组和达到最大
如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大

局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了）
全局最优：整个 数组和 达到最大

(2) 解题步骤：

1. 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
2. 从前向后遍历，遇到负数将其变为正数，同时K--
3. 如果K还大于0，那么反复转变数值最小的元素，将K用完
4. 求和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        if (nums.length == 1) return nums[0];
        int sum=0;
        // 排序：先把负数处理了
        Arrays.sort(nums);
        // 贪心点, 通过负转正, 消耗尽可能多的k
        for(int i=0;i<nums.length&&k>0;i++){
            if(nums[i]<0){
                nums[i]*=-1;
                k--;
            }
        }
        if(k%2==1){
            Arrays.sort(nums);
            nums[0]*=-1;
        } 
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        return sum;
    }
}

2. 加油站

(1) 暴力解法：

遍历每一个加油站为起点的情况，模拟一圈。

如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。

(2) 贪心算法(从全局进行贪心选择):

情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的

情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。

情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum=0;
        int min=Integer.MAX_VALUE;// 从起点出发，油箱里的油量最小值
        for(int i=0;i<cost.length;i++){
            int res=gas[i]-cost[i];
            curSum+=res;
            if(min>curSum) min=curSum;
        }
        if(curSum<0) return -1;            // 情况1                        
        if(min>=0) return 0;               // 情况2
        for(int i=cost.length-1;i>=0;i--){ // 情况3
            int res=gas[i]-cost[i];
            min+=res;
            if(min>=0) return i;
        }
        return -1;
    }
}

(3) 贪心算法

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因从i之前开始一定不行
全局最优：找到可以跑一圈的起始位置

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
       int start=0;
       int curSum=0;
       int totalSum=0;
       for(int i=0;i<gas.length;i++){
        curSum+=gas[i]-cost[i];
        totalSum+=gas[i]-cost[i];
        if(curSum<0){ // 当前累加rest[i]和 curSum一旦小于0
            start=i+1;// 起始位置更新为i+1
            curSum=0; // curSum从0开始
        }
       }
       if(totalSum<0) return -1; // 说明怎么走都不可能跑一圈了
       return start;
    }
}

3. 分发糖果

(1) 解题思路：

一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边

1.先确定右边评分大于左边的情况（也就是从前向后遍历）

局部最优：只要右边评分比左边大，右边的孩子就多一个糖果
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1

2.确定左孩子大于右孩子的情况一定要从后向前遍历！

3.如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。

局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。
全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。

(2) 解题步骤：

1. 先确定右孩子大于左孩子情况(从前向后遍历)
2. 再确认左孩子大于右孩子的情况(后向前遍历)
3. 取两遍遍历较大的那个，只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多

class Solution {
    public int candy(int[] ratings) {
        int[] candyVec=new int[ratings.length];
        Arrays.fill(candyVec,1);
        //先确定右孩子大于左孩子情况(从前向后遍历)
        for(int i=1;i<ratings.length;i++){ //从第二个开始
            if(ratings[i]>ratings[i-1]){ //右评分大于左
                candyVec[i]=candyVec[i-1]+1;
            }
        }
        //再确认左孩子大于右孩子的情况(后向前遍历)
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candyVec[i]=Math.max(candyVec[i],candyVec[i+1]+1);
            }
        }
        int result=0;
        for(int c:candyVec){
            result+=c;
        }
        return result;
    }
}