Gas station [problem analysis - > problem conversion - > greed]

Preface

The solution to many problems is not obvious / Combination of multiple knowledge points , Especially the scene question , Then it is more necessary to extract key problems , And analyzed .
Analyze the core requirements of the topic , We need to make appropriate knowledge contact / Combine / improvement , To complete the requirements .

One 、 Gas station

Two 、 logic analysis -> greedy

package everyday.greed;

//  Gas station 
public class CanCompleteCircuit {
    
    /* target： Choose a place to start walking , Arrive at each location , You can get the amount of oil at each location ( Can be installed , There is no upper limit ), Without taking one step, a certain amount of fuel will be consumed ( It can be understood as the distance )  You can see the amount of oil in each position , You should go from the place with the largest cumulative fuel . */
    public int canCompleteCircuit(int[] gas, int[] cost) {
    
        int n = gas.length;
        //  Calculate the difference between the amount of oil obtained at each position and the amount of oil it takes to take one step .
        int[] gap = new int[n];
        int surplus = 0;//  The amount of oil left 
        for (int i = 0; i < n; i++) {
    
            gap[i] = gas[i] - cost[i];
            surplus += gap[i];
        }
        //  As long as the total amount of fuel   Greater than or equal to   Total consumption , Then we must find a starting point , You can walk around , On the contrary, you can't find .
        //  Greedy thinking , One road has negative , Because the amount obtained is greater than or equal to the consumption , So the sum of the remaining half way must be positive , And positive + negative >=0
        if (surplus < 0) return -1;
        //  Double pointer to find the starting point .
        int begin = 0, sum = 0;
        for (int i = 0; i < n; i++) {
    
            if ((sum += gap[i]) < 0) {
    
                begin = i + 1;
                sum = 0;
            }
        }
        return begin;
    }
}

summary

1） Not all questions are to examine an obvious knowledge point , There are many problems that need to be analyzed / mining , Can be converted into relevant knowledge points .
2） Greedy thoughts .

reference

[1] LeetCode Gas station