【LEETCODE】模拟面试-134-Gas Station

新生

题目:

https://leetcode.com/problems/gas-station/

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.


分析:

This question is to find the start point where the car can complete a circuit.

Input: two arrays, one represents the gas at each station point, another one is cost when the car travels from point i to point i+1. **Output: **if the car can't finish a whole circuit, return -1, if yes, return the index of start point. Note: there maybe multiple solutions, but we just need one path.

The brute force method is that we can scan from 0 to last, each point will be considered as the start once. For each start, we will iterate all the following points in the circuit, and calculate the left gas. If the gas decreases below 0 during the process, this start point is failing, so we can move to next start point. If this start can complete the circuit, we can return its index, and no need to continue searching.

But how to optimize above method? We can reduce some repeated work. Take this data set as an example:

index:

0,

1,

2,

3,

4,

5,

6

gas:

3,

4,

3,

6,

7,

1,

2

cost:

2,

4,

5,

1,

5,

1,

3

Since we only care about the left gas at each point, we can firstly transform two arrays to one:

leftGas:

1,

0,

-2,

5,

2,

0,

-1

Suppose this, when we start from index=0, and we can move on till index=2, since the sum_leftGas here is 1, but we can't move to index=3. Then we can just ignore index=1,2 without considering them as start point, since they will be stuck at index_3 too.

And we continue from point index_3, it turns out all the left gas at each station can be >=0, so index_3 can be a start point.

This process is like a Queue: since we scan from 0 to 3, and 0,1,2 fails to be a start, so we pop them out, and continue from 3 to 4,5,6,0,1,2, till 3, a circuit finished.

But we can still optimize it. without pop 0,1,2 and add them again, we can just apply the structure Deque which can add and pop on both sides. Since the path will be a circuit, there's no need to delete any point, just add point on different sides, finally the points in de deque will combine a path.

So we start from 0, if the sum_gas will be >=0, we add next point on right side, otherwise, we add point on the left side.


Java

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost){
        //corner
        if ( gas == null || cost == null || gas.length != cost.length )
            return -1;
        
        //core
        int start = gas.length - 1;                     //用two pointer模拟deque,并不需要建立deque
        int end = 0;
        
        int gasLeftSum = gas[start] - cost[start];
        
        while ( start > end ){                          
            
            if ( gasLeftSum >= 0 ){                         //end开始并为加进来,所以先加,再右移
                gasLeftSum += gas[end] - cost[end];
                end++;
            }else{
                start--;
                gasLeftSum += gas[start] - cost[start];     //start最开始已经被加上了,所以先左移,再加油
            }   
        }
        
        return  gasLeftSum >= 0 ? start : -1;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2502 月之数(二进制,规律)

月之数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3444
来自专栏ml

HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

3726
来自专栏码匠的流水账

聊聊storm的GraphiteStormReporter

storm-core-1.2.2-sources.jar!/org/apache/storm/metrics2/reporters/GraphiteStormR...

1441
来自专栏码匠的流水账

聊聊storm tuple的序列化

storm-2.0.0/storm-client/src/jvm/org/apache/storm/executor/ExecutorTransfer.java

884
来自专栏小樱的经验随笔

Gym 100952D&&2015 HIAST Collegiate Programming Contest D. Time to go back【杨辉三角预处理,组合数,dp】

D. Time to go back time limit per test:1 second memory limit per test:256 megaby...

2966
来自专栏码匠的流水账

聊聊sentinel的ModifyRulesCommandHandler

本文主要研究一下sentinel的ModifyRulesCommandHandler

1271
来自专栏小樱的经验随笔

POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

3326
来自专栏ml

HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2856
来自专栏ml

HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

3334
来自专栏算法修养

HDU 5877 2016大连网络赛 Weak Pair(树状数组,线段树,动态开点,启发式合并,可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

40210

扫码关注云+社区

领取腾讯云代金券