美文网首页Leetcode
Leetcode.134.Gas Station

Leetcode.134.Gas Station

作者: Jimmy木 | 来源:发表于2019-10-31 10:24 被阅读0次

    题目

    背景: 有一辆汽车, 有n个汽油站.
    给定两个数组, 第一个数组表示每个汽油站的汽油量, 第二个数组表示走到下一个汽油站耗费的汽油.
    求汽车从哪个站出发可以回到该站, 回不到该站返回-1.

    Input: gas: [1,2,3,4,5], cost: [3,4,5,1,2]
    Output: 3
    Input: gas: [2,3,4], cost: [3,4,3]
    Output: -1
    

    思路1

    双循环. 假设从每个站出发, 看是否可以到达终点.
    时间复杂度O(n²)

    int canCompleteCircuit2(vector<int>& gas, vector<int>& cost) {
    
        vector<int> cache;
        int num = 0;
        for (int i = 0;i < gas.size();i++) {
            num = gas[i] - cost[i];
            if (num < 0) continue;
            for (int j = 1;j <= gas.size();j++) {
                int index = (i + j) % gas.size();
                num += gas[index] - cost[index];
                if (num < 0) {
                    break;
                }
            }
            if (num >= 0) {
                return i;
            }
        }
        return -1;
    }
    

    思路2

    通过数学变换, 如果汽油总量大于花费总量, 就一定可以回到终点.
    问题就是找到出发点, 出发点应该是最缺汽油的位置, 即总路程的汽油最少的位置.

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0, start = 0, min = INT_MAX;
        for(int i = 0; i < gas.size(); i++){
            sum += gas[i]-cost[i];
            if(sum < min){
                min = sum;
                start = i;
            }
        }
    
        return sum < 0 ? - 1 : (start+1) % gas.size();
    }
    

    总结

    貌似DP和递归都可以, 还是要使用常规方案解答. 在循环的时候可以添加缓存.

    相关文章

      网友评论

        本文标题:Leetcode.134.Gas Station

        本文链接:https://www.haomeiwen.com/subject/iemzvctx.html