加油站、、

狼啸风云

发布于 2023-10-07 16:04:03

1240

发布于 2023-10-07 16:04:03

文章被收录于专栏：计算机视觉理论及其实现

最容易想到的解法是：从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。

假设我们此前发现，从加油站

出发，每经过一个加油站就加一次油（包括起始加油站），最后一个可以到达的加油站是

（不妨设

）。这就说明：

第一个式子表明无法到达加油站 y的下一个加油站，第二个式子表明可以到达 y 以及 y 之前的所有加油站。

现在，考虑任意一个位于 x,y 之间的加油站 z（包括 x 和 y），我们现在考察从该加油站出发，能否到达加油站 y的下一个加油站，也就是要判断

与

之间的大小关系。

根据上面的式子，我们得到：

其中不等式的第二步、第三步分别利用了上面的第一个、第二个不等式。

从上面的推导中，能够得出结论：从 x,y之间的任何一个加油站出发，都无法到达加油站 y的下一个加油站。

在发现了这一个性质后，算法就很清楚了：我们首先检查第0个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

int