leetcode刷题-贪心算法

134. ��油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int len = gas.length;        // for(int i = 0; i = 0){                curr += gas[i];                curr -= cost[i];                i++;            }            sum += curr;        }        return sum >= 0 ? res : -1;    }}

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

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

  重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

  以这种方式修改数组后，返回数组 可能的最大和 。

  class Solution {    public int largestSumAfterKNegations(int[] nums, int k) {        int[] arr = new int[201];        int sum = 0;        for(int n : nums){            arr[n+100]++;            sum += n;        }        for(int i = 0; i  0; i++){            if(arr[i] != 0){                int min = Math.min(arr[i],k);                k -= min;                // i - 100   100 - i                arr[200-i] += min;                sum += (200-2*i)*min;            }        }        if(k % 2 != 0){            for(int i = 100; i  point2[1]) {                    return 1;                } else if (point1[1]  1){            res.add(-list.pollFirst() + list.peekFirst());        }        return res;    }}