加油站[问题分析-＞问题转换-＞贪心]

前言

很多题需要用到的解法不明显/多种知识点组合，尤其是场景题，那就更需要提取关键问题，并进行分析了。
分析题目的核心需求，需要做适当的知识点联系/组合/改进，才能够完成需求。

一、加油站

二、逻辑分析->贪心

package everyday.greed;

// 加油站
public class CanCompleteCircuit {
    
    /* target：选一个地点开始走，到达每个地点时，可以得到每个地点的油量(都可装，无上限)，而没走一步就会耗掉一定油量(可理解为路程量) 可以看看每个位置的油量，应该从可累计油量最大的地方走。 */
    public int canCompleteCircuit(int[] gas, int[] cost) {
    
        int n = gas.length;
        // 计算每个位置得到的油数和走一步要花费的油数差。
        int[] gap = new int[n];
        int surplus = 0;// 剩余油量
        for (int i = 0; i < n; i++) {
    
            gap[i] = gas[i] - cost[i];
            surplus += gap[i];
        }
        // 只要总得油量 大于等于 总消耗量，那么就一定能找到一个起点，可走一圈，反之则找不到。
        // 贪心思维，一条路有负，因为得到量大于等于消耗量，所以剩下半条路和一定为正，且正+负>=0
        if (surplus < 0) return -1;
        // 双指针找起点。
        int begin = 0, sum = 0;
        for (int i = 0; i < n; i++) {
    
            if ((sum += gap[i]) < 0) {
    
                begin = i + 1;
                sum = 0;
            }
        }
        return begin;
    }
}

总结

1）不是所有题就是考察一个明显的知识点，有很多题都是需要分析/挖掘，才能够转换成相关知识点。
2）贪心思想。

参考文献

[1] LeetCode 加油站