134. Gas Station - Medium

前往題目

想法

• 沒什麼想法，甚至覺得是不是要用DP

思路

一樣是Neetcode大大給的解法，也是我看到最好理解的

1. 一開始先藉由兩個array的各自的總和比較，就可以看出是否沒有解，也就是-1。因為gas的sum < cost的sum的時候代表就算從汽油最充足的地方開始一樣不可能抵達，因為起點也是終點
2. 接著就知道一定會有解，那只要找到最靠左的gas[i] - cost[i]不為零的起始點就一定是答案，因為一定有解，且只有唯一解

這時候八成會想，為什麼不會在中間變成負的，但其實有解，只是在後頭。這種情況應該會產生多種解，所以不可能有這種情況，題目已經保證有解的話就是唯一解。至於為什麼我說”應該”，因為我不會證明🤣寫一些測資的結果都是有多種解，所以不會出現有中間斷掉的情況

Code

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // No solution
        if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) {
            return -1;
        }

        // Guarantee a solution
        int total = 0;
        int res = 0;

        // Loop through the station
        for (int i = 0; i < gas.length; ++i) {
            // Cal. the difference
            total += gas[i] - cost[i];

            // Skip the station that can't even start from
            if (total < 0) {
                total = 0;
                res = i + 1; // Result will be the next station
            }  
            
        }

        return res;
    }
}

2024/04/18

• 忘了這題的兩個關鍵點
  1. 汽油的總和如果比需要的少就一定沒有解
  2. 有解的話只要找到可以開始的點就一定是解，因為只有唯一解