/ Data Structure and Algorithms  

Leetcode 134. Gas Station

Question



Just understand this question as the picture below:



Each node represents the amount of oil added, and each edge represents the amount of oil consumed. The meaning of the question is to ask us which node we start from and return to that node. We can only go clockwise.

Solution

For this question, we can just use Brute Force.

Consider whether starting from the 0 point, and can return to the 0 point.

Consider whether starting from the 1 point, and can return to the 1 point.

Consider whether starting from the 2 point, and can return to the 2 point.

…

Consider whether starting from the n point, and can return to the n point.

Since it is a circle, we need to take the remainder when we get the next point.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// already assume gas and cost are non-empty and have same length

// consider starting from each point
for (int i = 0; i < gas.length; i++) {
    int startIndex = i;

    // initial gas
    int remaining = gas[startIndex];

    // check if remaining can reach next
    while (remaining - cost[startIndex] > 0) {
        // minus cost and add gas
        remaining = remaining - cost[startIndex] + gas[(startIndex + 1) % gas.length];

        startIndex = (startIndex + 1) % gas.length;

        // if returned to i
        if (startIndex == i) {
            return i;
        }
    }
}

// looped all nodes, not node is possible
return -1;