LeetCode Gas Station 数学

本文主要是介绍LeetCode Gas Station 数学，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

There are n gas stations along a circular route, where the amount of gas at the \(i\)th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the \(i\)th station to its next \((i + 1)\)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return \(-1\). If there exists a solution, it is guaranteed to be unique

Solution

给定一个圆环，有若干个加油站，问是否存在一个起始点使得空油箱的汽车跑完一周。不妨记：

假设从 \(i\) 开始，此时到达 \(i+1\) 需要满足：

类似地，到达 \(i+2\) 需要满足：

可以发现这就是前缀和，对于环形问题，我们可以摊开为一个 \(2n\) 的序列即可。所以只需要所有的前缀和非负即可

class Solution {
private:
    int dif[200005];
    int ans = 0;
    
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int ck = 0;
        for(int i=0;i<n;i++)dif[i] = gas[i]-cost[i], ck += dif[i];
        for(int i=n;i<2*n;i++)dif[i] = dif[i-n];
        int fg=0;
        if(ck<0)return -1;
        
        int tank_V = 0, st = 0;
        for(int i=0;i<2*n;i++){
            tank_V += dif[i];
            if(tank_V<0){
                tank_V = 0;
                st = i+1;
            }
        }
        return st%n;
    }
};

这篇关于LeetCode Gas Station 数学的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！