链接:https://leetcode.cn/problems/gas-station/solution/-by-xun-ge-v-9ftb/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
解题思路
【暴力解法】
暴力的方法很明显就是O(n^2)的,遍历每一个加油站为起点的情况,模拟一圈。
如果跑了一圈,中途没有断油,而且最后油量大于等于0,说明这个起点是ok的。
暴力的方法思路比较简单,但代码写起来也不是很容易,关键是要模拟跑一圈的过程。
for循环适合模拟从头到尾的遍历,而while循环适合模拟环形遍历,要善于使用while!
但是会超时,需要优化。。。
【全局-贪心】
从全局进行贪心选择,情况如下:
【局部-贪心】
从上述可以看出,如果我们能绕环路行驶一周,在寻找第一个起点时只需要满足一个条件即可:
因为如果累加油量小于当前位置长度,那么肯定就到不了当前点,居然到不了,又能绕环路行驶一周,那就只能从当前位置出发
【暴力解法】
- int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
- for (int i = 0; i < costSize; i++) {
- int rest = gas[i] - cost[i]; // 记录剩余油量
- if(rest < 0) continue; //适当剪枝
- int index = (i + 1) % costSize;
- while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈
- rest += gas[index] - cost[index];
- index = (index + 1) % costSize;
- }
- // 如果以i为起点跑一圈,剩余油量>=0,返回该起始位置
- if (rest >= 0 && index == i) return i;
- }
- return -1;
-
- }
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/gas-station/solution/-by-xun-ge-v-9ftb/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
【全局-贪心】
- int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
- int curSum = 0;
- int min = INT_MAX; // 从起点出发,油箱里的油量最小值
- for (int i = 0; i < gasSize; i++) {//先统计整体油量
- int rest = gas[i] - cost[i];
- curSum += rest;
- if (curSum < min) {
- min = curSum;
- }
- }
- if (curSum < 0) return -1; // 情况1
- if (min >= 0) return 0; // 情况2
- // 情况3
- for (int i = gasSize - 1; i >= 0; i--) {//遍历前面油站填油
- int rest = gas[i] - cost[i];
- min += rest;
- if (min >= 0) {
- return i;
- }
- }
- return -1;
- }
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/gas-station/solution/-by-xun-ge-v-9ftb/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
【局部-贪心】
- int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
- int curSum = 0;
- int min = INT_MAX; // 从起点出发,油箱里的油量最小值
- for (int i = 0; i < gasSize; i++) {//先统计整体油量
- int rest = gas[i] - cost[i];
- curSum += rest;
- if (curSum < min) {
- min = curSum;
- }
- }
- if (curSum < 0) return -1; // 情况1
- if (min >= 0) return 0; // 情况2
- // 情况3
- for (int i = gasSize - 1; i >= 0; i--) {//遍历前面油站填油
- int rest = gas[i] - cost[i];
- min += rest;
- if (min >= 0) {
- return i;
- }
- }
- return -1;
- }
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/gas-station/solution/-by-xun-ge-v-9ftb/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。