Gas Station Solutions in C++

// Source : https://oj.leetcode.com/problems/gas-station/
// Author : Hao Chen
// Date   : 2014-10-11



class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int current = 0;
        int start = gas.size(); //start from the end to beginning
        int total = 0;
        
        do {
            if (total + gas[current] - cost[current] >= 0) {
                total += (gas[current] - cost[current]);
                current++; // can go from current to current+1
            }else{
                start--; //not enough gas, try to start the one before origin start point.
                total += (gas[start] - cost[start]);
            }
        } while(current != start);
        
        return total>=0 ? start % gas.size() : -1;
    }
};

#include <vector>
using std::vector; 

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int tank{0}, start{0}, stored{0};
        for (decltype(gas.size()) i=0; i<gas.size(); ++i)
            if ((tank += gas[i] - cost[i]) < 0) {
                start = i + 1;
                stored += tank; 
                tank = 0;
            }
        return (tank + stored) < 0 ? -1 :start;
    }
};

/// Source : https://leetcode.com/problems/gas-station/
/// Author : liuyubobobo
/// Time   : 2019-03-16

#include <iostream>
#include <vector>

using namespace std;


/// Greedy
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();

        int minv = INT_MAX, res = -1, cur = 0;
        for(int i = 0; i < n; i ++){
            cur += gas[i] - cost[i];
            if(cur < minv) minv = cur, res = i;
        }
        if(cur < 0) return -1;
        return (res + 1) % n;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/gas-station/
/// Author : liuyubobobo
/// Time   : 2019-03-16

#include <iostream>
#include <vector>

using namespace std;


/// Simulation
/// This solution is more intuitive, see Leetcode Official Solution for details:
/// https://leetcode.com/problems/gas-station/solution/
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();

        int res = 0, total = 0, cur = 0;
        for(int i = 0; i < n; i ++){
            cur += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(total <= 0) res = (i + 1) % n, total = 0;
        }
        if(cur < 0) return -1;
        return res;
    }
};


int main() {

    return 0;
}