4.＜tag-贪心算法＞lt.1005.K次取反后最大化的数组和 + lt.134. 加油站 dbc

lt.1005.K次取反后最大化的数组和 [案例需求]

[思路分析]

[代码实现]

lt.134. 加油站 [案例需求]

[思路分析一, 暴力解法] [代码实现]

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //1. 暴力遍历
        //遍历cost的每个i(以cost[i]为起点,), 记录每经过一个cost时的剩余油量, 等待走了一圈时, 
        // 判断剩余油量是否> 0
        int len = cost.length;

        
        for(int i = 0; i < len; i++){
            int rest = gas[i] - cost[i]; //当前位置的剩余油量,
            int index = (i + 1) % cost.length; // 当前位置的下一个未知

            //开始跑圈
            //剩余油量 > 0 && 已经走了一圈
            while(rest > 0 && index != i){
                rest += gas[index] - cost[index]; //剩余油量
                index = (index + 1) % cost.length;
            } 
            //回到起始位置了
            if(rest >= 0 && index == i)return i;
        }

        return -1;
    }
}

[思路分析二, 贪心解法] [代码实现]

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //2. 贪心
        //剩余油量 res[i] = cost[i] - gas[i];
        //curGasSum += res[i];
        //如果小于0. 说明i之前包括i的不可能作为起点;
        int len = gas.length;

        int curGasSum = 0;
        int totalGasSum = 0;
        int start = 0;

        for(int i = 0; i < len; i++){
            curGasSum += gas[i] - cost[i];
            totalGasSum += gas[i] - cost[i];

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

        if(totalGasSum < 0)return -1;

        return start;
    }
}