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!

# [closed] gas station problem

 0 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: 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. If there is no such station, return -1. Input: vector gas, int L, int K Output: int asked 10 Jul '13, 19:20 hx0 46●3 accept rate: 16% 1337c0d3r ♦♦ 1.2k●14●89●171

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

 4 ``````int canCompleteCircuit(vector &gas, vector &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; } `````` answered 29 Sep '13, 09:49 Kalman 51●3 accept rate: 0%
 0 is this a DP problem or greedy? I met this in an interview, but I couldn't finish it, anyone have ideas? answered 14 Jul '13, 19:01 hx0 46●3 accept rate: 16%
 0 ``````int canCompleteCircuit(vector &gas, vector &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 diff(N*2, 0); for (int i=0; i= N) return -1; } } `````` answered 29 Sep '13, 07:59 syrcx 11●2 accept rate: 0%
 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 &gas, vector &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; } }; `````` answered 29 Sep '13, 08:27 nriver 76●5 accept rate: 0%
 0 class Solution { public: ``````int canCompleteCircuit(vector &gas, vector &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; } `````` }; answered 29 Sep '13, 18:35 Junjie Qi 1 accept rate: 0%
 0 ``````public int canCompleteCircuit(int[] gas, int[] cost) { int i,start,sum,len = gas.length; for(i=0;i=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=0; start++); //find first negative diff if(start==len) break; //we've checked everything, there is no solution } return -1; } `````` answered 01 Oct '13, 22:37 SPICHANOK DZ... 76●3 accept rate: 5%
 0 ``````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; } `````` answered 02 Oct '13, 00:14 zhangxu 11●2 accept rate: 0%
 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; } `````` answered 09 Oct '13, 22:55 Nathan 34●4 accept rate: 0%
 0 why most of the answers have no explanation? answered 15 Oct '13, 18:19 hustwcw 11●1 accept rate: 0%
 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 &gas, vector &cost) { // Note: The Solution object is instantiated only once and is reused by each test case. vector net; int n=gas.size(); for (int i=0; i=0) return i; } return -1; } `````` answered 15 Oct '13, 22:20 denny5 11●2 accept rate: 0%

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• Indent code by 4 spaces.
• 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