This series uses the IDEA+LEETCODE EDITOR plug-in. Topic Description:

//There are n gas stations along a circular route, where the amount of gas at th
//e ith station is gas[i]. 
//
// You have a car with an unlimited gas tank and it costs cost[i] of gas to trav
//el from the ith station to its next (i + 1)th station. You begin the journey wit
//h an empty tank at one of the gas stations. 
//
// Given two integer arrays gas and cost, return the starting gas station's inde
//x if you can travel around the circuit once in the clockwise direction, otherwis
//e return -1. If there exists a solution, it is guaranteed to be unique 
//
// 
// Example 1: 
//
// 
//Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
//Output: 3
//Explanation:
//Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4
/ / = 4
//Travel to station 4. Your tank = 4 - 1 + 5 = 8
//Travel to station 0. Your tank = 8 - 2 + 1 = 7
//Travel to station 1. Your tank = 7 - 3 + 2 = 6
//Travel to station 2. Your tank = 6 - 4 + 3 = 5
//Travel to station 3. The cost is 5. Your gas is just enough to travel back to 
//station 3.
//Therefore, return 3 as the starting index.
// 
//
// Example 2: 
//
// 
//Input: gas = [2,3,4], cost = [3,4,3]
//Output: -1
//Explanation:
//You can't start at station 0 or 1, as there is not enough gas to travel to the
// next station.
//Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
//
//Travel to station 0. Your tank = 4 - 3 + 2 = 3
//Travel to station 1. Your tank = 3 - 3 + 3 = 3
//You cannot travel back to station 2, as it requires 4 unit of gas but you only
// have 3.
//Therefore, you can't travel around the circuit once no matter where you start.
//
// 
//
// 
// Constraints: 
//
// 
// gas.length == n 
// cost.length == n 
// 1 <= n <= 104 
// 0 <= gas[i], cost[i] <= 104 
Copy the code

First of all, I will give you a circle of gas stations. What is a circle rather than a row? Because they’re asking you to go clockwise from any gas station to all the gas stations. It then gives you your gas mileage from one station to the next and how much you can fill up at the current station. Make you wonder which gas station you can walk all the way from. When you look at the loop and the array parameters given, you should think about doing the loop by taking % mod to the subscript, rather than having to initialize it to 0 again when the array reaches its maximum subscript value, a little trick that makes your code more elegant. LC has a lot of loopy problems. Don’t see what difficulties, first directly to a version of violence solution, the idea is very simple: cycle gas station, use the current as the starting point, test whether to finish. But this solution is also very poor performance, because it’s still linear thinking. How to optimize a non-recursive traversal algorithm is the focus of this video.

Third, AC code: first show the violent version.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // First gas is greater than or equal to cost to complete a lap
        int sumGas = 0;
        for (int i : gas) {
            sumGas += i;
        }
        int sumCost = 0;
        for (int i : cost) {
            sumCost += i;
        }
        if(sumGas<sumCost){
            return -1;
        }
        // You can finish the race by walking through the train station
        for (int i = 0; i < gas.length; i++) {
            // Include the current station
            int visited = 1;
            int tmpIndex = i;
            // The remaining gasoline
            int totalGas = 0;
            // Loop subscript with %gas.length
            while(true){
                totalGas += gas[tmpIndex%gas.length];
                // Can you take the next stop
                if(totalGas>=cost[tmpIndex%gas.length]){
                    totalGas -= cost[tmpIndex%gas.length];
                    visited ++;
                    tmpIndex ++;
                    if(visited >= gas.length){
                        returni; }}else{
                    break; }}// Termination conditions
            if(visited >= gas.length){
                returni; }}return -1; }} Solution successful: Execution time:95Ms, defeated18.81% Java user memory consumption:39MB, defeated6.44% of Java usersCopy the code

Now we start to optimize, and first implement two conclusions: — When total fuel consumption > total fuel consumption, there is no solution (in the previous solution, it is judged independently outside the cycle of the gas station, which can be added into the ergotation of the gas station, and the optimization range is not large). — Go through the gas station from the beginning, if the previous balance lastRes + gas[I] -cost [I]<0, I must not be the originating station. Because it is clockwise, the next gas station can only be used as the hypothetical starting station.

Gas: 1, 2, 3, 4, 5 cost: 3, 5, 1, 2, 4 Start from index=1, lastRes + gas[1] -cost [1]<0, 1 is not the starting point, use 2; From index=2, lastRes + gas[2] -cost [2]>=0, can be used as a starting point, go down to index=3, lastRes + gas[3] -cost [3]>=0, go down to index=4, LastRes + gas[3] -cost [3]>=0, you can go down, at which point the cycle ends.

Now you have to ask, why does the loop end at the last stop? Shouldn’t I go back to index=0? This is the key point of poor performance of the previous violent solution. For index, which cannot be used as a starting point, we only need to know that it cannot be used as a starting point. Whether it can be finished at last can be judged by (total fuel consumption – total fuel consumption). For this problem, there is a unique solution, which means that once a starting point has exhausted all the gas stations behind it, there is no need to start from the beginning, because it has already been determined that it cannot be used as a starting point. For example, when the last gas station reaches 0, lastRes must be 0. As long as gas[6] -cost [6]>=0, there is no need to judge the first 6 points. Only need to rely on the overall total fuel – total fuel consumption is greater than or equal to 0. 1, 1, 1, 1, 1, 0

   class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // The total amount of remaining oil is less than 0
        int sumRes = 0;
        // The value to return is iterated from subscript 0 of the gas station array
        int index = 0;
        // The amount of oil left in the process starting from a station
        int tmpRes = 0;
        for (int i = 0; i < gas.length; i++) {
            // Look at the total amount of oil remaining globally, instead of sumgas-sumcost in the violent solution
            sumRes += gas[i] - cost[i];
            tmpRes += gas[i] - cost[i];
            if(tmpRes < 0) {// The current gas station can not go to the next gas station
                // You can only go to the next gas station
                index = i + 1;
                tmpRes = 0; }}return sumRes < 0? -1: index; }}Copy the code
Solution successful: Execution time :0 ms, beat 100.00% Java user memory consumption :38.4 MB, beat 95.16% Java usersCopy the code

Iv. Summary:

  1. Non-recursive traversal algorithms, there’s still a lot of double counting, and the way to optimize this kind of problem is to find this part.
  2. Understand that array circles can be solved with %.
  3. Grasp both parts and parts.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign