⓺➂ Gas Station

Top Interview 150, leetcode medium, C++, Algorithm

Today’s code

Idea1 Time Limit Exceeded

這就是模擬法的方式，去推演每一次出發的情形，但這樣就會很費時，與做許多次重複的事情。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        vector<int> tank(length);
        int ans_index = 0;
        
        bool is_arrived = true;
        for(int i = 0; i < length; i++){
            tank[i] = gas[i] - cost[i];
        }

        for(; ans_index < length; ans_index++){
            is_arrived = true;
            int tmp_gas = 0;
            for(int j = ans_index; j < length; j++){
                tmp_gas += tank[j];
                if(tmp_gas < 0){
                    is_arrived = false;
                    break;
                }
            }

            if(!is_arrived){
                continue;
            }
            
            for(int i = 0; i < ans_index; i++){
                tmp_gas += tank[i];
                if(tmp_gas < 0){
                    is_arrived = false;
                    break;
                }
            }


            if(is_arrived){
                
                break;
            }
        }
        
        if(is_arrived){
            return ans_index;
        }else{
            return -1;
        }

    }
};

Idea2 by hi-malik

1. 選定的起始位置必須是大於等於零的整數，表示可以順利到達下一個加油站。
2. 除了起始位置之後都是累加的（tmp_tunk）方式去判斷，能否順利到達下一個加油站。
3. 也是卡關最久的一個限制，就是全部的累計（total_tunk），注意這裡的全部累積跟第二點的起始位置之後的累計，是不一樣的。這裡的全部累計，是在判斷整個走完能不能完美的繞一圈。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        int total_tunk = 0;
        int tmp_tunk = 0;
        int start_index = 0;

        for(int i = 0; i < length; i++){
            tmp_tunk += gas[i] - cost[i];
            total_tunk += gas[i] - cost[i];

            if(tmp_tunk < 0){
                start_index = i + 1;
                tmp_tunk = 0;
            }


        }

        if(total_tunk >= 0 && tmp_tunk >= 0){
            return start_index;
        }else{
            return -1;
        }

    }
};

參考

https://leetcode.com/problems/gas-station/solutions/1706142/java-c-python-an-explanation-that-ever-exists-till-now