一. 贪心算法相关题目

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

贪心

思路

将数组按照绝对值降序排序后从最大数值开始遍历遇到复数就取反,k减一,如果遍历完之后k为奇数就对绝对值最小的数取反求和

class Solution {

    public int largestSumAfterKNegations(int[] nums, int k) {
        //第一步按照绝对值排序降序
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        //第二步从绝对值大的开始遍历遇到复数就取反,k--
        for (int i = 0; i < nums.length; i++) {
            if (k>0&& nums[i]<0){
                k--;
                nums[i] = nums[i]*-1;
            }
        }
        // 第三步如果k仍大于0且k是奇数就对最小的取反
        if (k>0 && k%2>0){
            nums[nums.length-1] = nums[nums.length-1]*-1;
        }
        // 第四步求和

        return Arrays.stream(nums).sum();
    }
}

134.加油站

贪心

思路

从第零站开始计算剩余油量,如果剩余油量小于0那么[0,i]区间无法作为出发站重i加一站开始判断,剩余油量清零
在遍历过程中还需要计算总剩余油量,如果遍历完毕总剩余油量小于0那么就证明无论从哪一个起点开始都无法完整的走一圈

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //当前站剩余油量
        int curSum = 0;
        //所有站剩余油量
        int totalSum = 0;
        //出发站
        int startIndex = 0;
        //从第零站开始遍历当前站剩余油量,如果当前站剩余油量小于0那么就从i+1站开始出发
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum<0){
                curSum = 0;
                startIndex = i+1;
            }
        }
        if (totalSum<0) return -1;
        return startIndex;
    }
}

135.分发糖果

贪心

思路

优先判断一边的糖果分发情况再判断另一边
搜先创建一个等长数组初始化每个人的糖果都为1
从前往后遍历如果前一位的评分小于当前位就把当前位的评分等于前一位评分加一
从后往前遍历,如果但当前位的评分大于后一位的就取当前位评分和后一位评分加一的最大值

class Solution {
    public int candy(int[] ratings) {
        int[] candys = new int[ratings.length];
        Arrays.fill(candys,1);
        //从前往后
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i]>ratings[i-1]) candys[i] = candys[i-1]+1;
        }
        //从后向前
        for (int i = ratings.length-2; i>=0; i--){
            if (ratings[i]>ratings[i+1]) candys[i] = Math.max(candys[i],candys[i+1]+1);
        }

        return Arrays.stream(candys).sum();
    }
}