leetcode 134. Gas Station

╰半夏微凉° 2022-07-30 13:57 87阅读 0赞

There are N gas stations along a circular route, where the amount of gas at station i is `gas[i]`.

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

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:  
The solution is guaranteed to be unique.

很明显，起点要从gas-cost大于零的地方开始，如果有连续的这样的点，只选取第一个这样的点。

class Solution {
    public:
    	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    		if (gas.size() == 1)
    		{
    			if (gas[0] >= cost[0])
    				return 0;
    			else
    				return -1;
    		}
    		vector<int>starter;
    		int k = 0;
    		while (k < gas.size())
    		{
    			if (gas[k] - cost[k] > 0)
    			{
    				int kk = k;
    				starter.push_back(k);
    				while (kk < gas.size() && gas[kk] - cost[kk] >= 0)
    					kk++;
    				k = kk;
    			}
    			k++;
    		}
    		for (int i = 0; i < starter.size(); i++)
    		{
    			int rem = 0;
    			while (rem >= 0)
    			{
    				rem = gas[starter[i]] - cost[starter[i]];
    				int kk = starter[i];
    				int cnt = 1;
    				while (rem >= 0)
    				{
    					kk++;
    					if (kk == gas.size())
    						kk = 0;
    					rem += gas[kk] - cost[kk];
    					cnt++;
    					if (cnt == gas.size() && rem >= 0)
    						return starter[i];
    				}
    			}
    		}
    		return -1;
    	}
    };

accept

发表评论取消回复

表情：

评论列表（有 0 条评论，87人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 134. Gas Station (贪心)

目描述：有i个加油站 gas\[i\]代表在第i个加油站可以加到的油 cost\[i\]代表从第i个加油站到第i+1个加油站消耗的油题目想问，从下标为几的节点...

Love The Way You Lie/ 2024年04月18日 11:51/ 0 赞/ 6 阅读

相关 Gas Station--LeetCode

There are N gas stations along a circular route, where the amount of gas at stationi is`

野性酷女/ 2022年08月07日 13:54/ 0 赞/ 93 阅读

相关 leetcode 134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is

╰半夏微凉°/ 2022年07月30日 13:57/ 0 赞/ 88 阅读

相关 LeetCode134—Gas Station

1.原题原题链接：[LeetCode134][] There are N gas stations along a circular route, where the

水深无声/ 2022年07月17日 02:24/ 0 赞/ 116 阅读

相关 leetcode 134. Gas Station

1、题目 There are N gas stations along a circular route, where the amount of gas at stat

水深无声/ 2022年06月08日 11:24/ 0 赞/ 101 阅读

相关 leetcode 134. Gas Station 加油站问题 + 很值得思考

There are N gas stations along a circular route, where the amount of gas at station i is

谁践踏了优雅/ 2022年06月08日 05:57/ 0 赞/ 122 阅读

相关 LeetCode 134.Gas Station (加油站)

题目描述：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 `gas[i]`升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗

以你之姓@/ 2022年05月08日 10:06/ 0 赞/ 157 阅读

相关 [leetcode]gas-station加油站（贪心）

问题描述： There are N gas stations along a circular route, where the amount of gas at sta

缺乏、安全感/ 2022年03月11日 13:25/ 0 赞/ 173 阅读

相关 134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station

淩亂°似流年/ 2022年02月15日 19:12/ 0 赞/ 176 阅读

相关 LeetCode : 134. Gas Station加油

试题 There are N gas stations along a circular route, where the amount of gas at station

冷不防/ 2021年06月12日 20:36/ 0 赞/ 375 阅读