Old discuss is read-only now. Please go to New LeetCode Discuss for your questions and answers!

User account in old discuss will not integrate to the new one, but new discuss is integrated with new online judge, which means, if you already have an account in new online judge, you can access new discuss immediately!

If you want to ask for question relevant to the posts in old discuss, please copy content as part of your question, only old discuss link is NOT ALLOWED!

Please read the FAQ in new LeetCode Discuss to help yourself making the best use of Discuss!

There is a circle round, and gas stations are distributed averagely along the round, every station located in each L km, given N stations, so the total length of the road is N * L (km), and each station(numbered from 0 ~ N-1) has gas[i] gas, and given K as the gas needed per km, and the car's gas tank has infinity capacity, the problem is to find the following:

  1. Is there a possible start station that the car can go around the road and back to the original place? if there is return it, if there is more than 1, return any of such.
  2. If there is no such station, return -1.

Input: vector<int> gas, int L, int K

Output: int

asked 10 Jul '13, 19:20

hx0's gravatar image

hx0
463
accept rate: 16%

closed 25 Oct '13, 06:25

1337c0d3r's gravatar image

1337c0d3r ♦♦
1.2k1489171

The question has been closed for the following reason "bulk close" by 1337c0d3r 25 Oct '13, 06:25


12next »

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
  int sum = 0;
  int total = 0;
  int j = -1;
  for(int i = 0; i < gas.size() ; ++i){
    sum += gas[i]-cost[i];
    total += gas[i]-cost[i];
    if(sum < 0){
      j=i; sum = 0; 
    }
  }
  return total>=0? j+1 : -1;
}
link

answered 29 Sep '13, 09:49

Kalman's gravatar image

Kalman
513
accept rate: 0%

edited 29 Sep '13, 10:06

is this a DP problem or greedy? I met this in an interview, but I couldn't finish it, anyone have ideas?

link

answered 14 Jul '13, 19:01

hx0's gravatar image

hx0
463
accept rate: 16%

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    if (gas.size() != cost.size() || gas.size() == 0) return -1;

    int N = gas.size();
    vector<int> diff(N*2, 0);
    for (int i=0; i<N; i++) {
        diff[i] = gas[i] - cost[i];
        diff[i+N] = diff[i];
    }

    int start_index = 0;
    int total_diff = 0;
    for (int i=0; i<N*2-1; i++) {
        total_diff += diff[i];
        while (total_diff < 0) {
            total_diff -= diff[start_index];
            start_index++;
        }
        if (start_index + (N-1) == i) return start_index;
        if (start_index >= N) return -1;
    }
}
link

answered 29 Sep '13, 07:59

syrcx's gravatar image

syrcx
112
accept rate: 0%

Below is a solution to the corresponding OJ:

Starting from the first gas station, move from it till the car cannot move any more. And the stations passed won't be a valid starting station. Continue test the next gas station till find a valid one or no such a station exist.

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int tank = -1;
        int ret = -1;

        for (int i = 0; i < gas.size(); ++i) {
            int tmp = gas[i] - cost[i];
            if (tank >= 0) {
                tank += tmp;
                ret = tank < 0 ? -1 : ret;
            } else if (tmp >= 0) {
                tank = tmp;
                ret = i;
            }
        }

        for (int i = 0; tank >= 0 && i < ret; ++i)
            tank += gas[i] - cost[i];

        return tank >= 0 ? ret : -1;
    }
};
link

answered 29 Sep '13, 08:27

nriver's gravatar image

nriver
765
accept rate: 0%

class Solution { public:

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
   int index = 0;
   while(index < gas.size()){
       if(cost[index] > gas[index]){
           ++index;
           continue;
       }
       int sum = gas[index] - cost[index];
       int i = index + 1;
       int next_index = i % gas.size();
       while(i % gas.size() != index){
           sum += gas[i % gas.size()] - cost[i % gas.size()];
           if(sum < 0) {
               next_index = i % gas.size();
               break;
           }
           ++i;
       }
       if(i % gas.size() == index) return index;
       index = next_index > index ? next_index: index + 1;
   }
   return -1;
}

};

link

answered 29 Sep '13, 18:35

Junjie%20Qi's gravatar image

Junjie Qi
1
accept rate: 0%

public int canCompleteCircuit(int[] gas, int[] cost) {
    int i,start,sum,len = gas.length;

    for(i=0;i<len;i++) gas[i]-=cost[i]; //let's keep difference in gas[]

    start=0;
    while(true){

        for(    ;start<len && gas[start]<0; start++); //find first non-negative diff

        if(start==len) break;  //we've checked everything, there is no solution

        for(sum=0,i=start;i<(len+start) && sum>=0;i++) sum+=gas[i%len]; //check route, if sum is negotive at any step then we used wrong starting pos.

        if(sum>=0 && i==(len+start)) return start; //since it's should be unique, then we've found it!

        for(    ;start<len && gas[start]>=0; start++); //find first negative diff

        if(start==len) break;   //we've checked everything, there is no solution 
    }

    return -1;
}
link

answered 01 Oct '13, 22:37

SPICHANOK%20DZMITRY's gravatar image

SPICHANOK DZ...
763
accept rate: 5%

public boolean canCompleteCircuit(int[] gas, int[] cost) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
        return false;
    }
    if (gas.length != cost.length)  return false;
    int n = gas.length;

    int start = 0, end = 0, gasRemain = 0;
    while (start < n) {
        while (gasRemain >= 0) {
            gasRemain += gas[end] - cost[end];
            end = (end + 1) % n;
            if (end == start && gasRemain >= 0) return true;
        }
        while (gasRemain < 0 && start < n) {
            gasRemain -= gas[start] - cost[start];
            start = start + 1;
        }
    }

    return false;
}
link

answered 02 Oct '13, 00:14

zhangxu's gravatar image

zhangxu
112
accept rate: 0%

public int canCompleteCircuit(int[] gas, int[] cost) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int tank=gas[0]-cost[0];
    int len=gas.length;
    int idx1=0,idx2=len;
    while(idx1!=idx2-1){
        if(tank>=0){
            idx1++;
            tank+=gas[idx1]-cost[idx1];

        }else{
            idx2--;
            tank+=gas[idx2]-cost[idx2];

        }
    }
    return tank>=0?idx2%len:-1;
}
link

answered 09 Oct '13, 22:55

Nathan's gravatar image

Nathan
344
accept rate: 0%

why most of the answers have no explanation?

link

answered 15 Oct '13, 18:19

hustwcw's gravatar image

hustwcw
111
accept rate: 0%

At each station, given the gas and cost, the net gas left when arriving next station is gas[i] - cost[i].

Each station has a net gas < 0 will not be a start station. For each station, if there is an accumulation net gas < 0, this station can't be a start station. Also, if the accumulation gas from station i to j is negative, all these stations can't be start station. (assumed that we checked it was still position before station j. If we started from any station from i to j, it will become negative after j). So we can safely loop only one pass.

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    vector<int> net;
    int n=gas.size();
    for (int i=0; i<n;i++)
    {
        net.push_back(gas[i] - cost[i]);
    }

    for (int i=0; i<n; i++)
    {
        if (net[i] <0) continue;

        int nSum = 0;
        for (int j=0; j<n; j++)
        {
            nSum += net[(i+j)%n];
            if (nSum < 0)
            {
                i += j;
                break;
            }
        }
        if (nSum>=0) 
            return i;
    }

    return -1;
}
link

answered 15 Oct '13, 22:20

denny5's gravatar image

denny5
112
accept rate: 0%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • Indent code by 4 spaces.
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×4

Asked: 10 Jul '13, 19:20

Seen: 3,032 times

Last updated: 25 Oct '13, 06:25