神刀安全网

C++ Coding Exercise – 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.The solution is guaranteed to be unique.

Submit your solution at: https://leetcode.com/problems/gas-station/

It is obvious that there isn’t any solution (should return -1) if the sum of gas[] is smaller than sum of cost[] array. We try and record the start position. If at any time, we find that the tank + gas[i] – cost (current fuel amount) is less than zero, we find an impossible route. In this case, we set the start position at next station, and re-initialize the fuel amount of the car to zero.

There is an important fact that if we run out the gas at station i then starting anywhere from 0 to i – 1 would be futile. That is due to: the accumulated sum from station 0 to station i-1 is positive, i.e. Removing a positive number will not make the sum bigger at station i .

class Solution { public:     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {         int n = gas.size();         int start = 0;         int total = 0;         int tank = 0;         for (int i = 0; i < n; i ++) {             int dif =  gas[i] - cost[i];             tank += dif;       // extra fuel in tank             total += dif;                  if (tank < 0) {                 start = i + 1; // should start from next                 tank = 0;      // empty the tank             }         }         // if total cost is larger than total gas, then impossible         return total < 0 ? -1 : start;     } };
class Solution { public:     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {         int n = gas.size();         int start = 0;         int total = 0;         int tank = 0;         for (int i = 0; i < n; i ++) {             int dif =  gas[i] - cost[i];             tank += dif;       // extra fuel in tank             total += dif;                  if (tank < 0) {                 start = i + 1; // should start from next                 tank = 0;      // empty the tank             }         }         // if total cost is larger than total gas, then impossible         return total < 0 ? -1 : start;     } };

The requirements for a solution are: We finish iterating the array and we have the last-recorded start position, and the C++ Coding Exercise – Gas Station

is bigger than zero.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – Gas Station

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址