[LintCode/LeetCode] Gas Station

hedge_hog 发布于2019-08-14 15:21 / 905人阅读

摘要：看到这个题目，怎样可以不把它当成一个环路来分析，以及减少多余的空间呢例如，我们引入单次剩余油量，剩余油量和，总剩余油量和，以及可行起点四个参数。大体上说，只要，一定有解。所以跳过这个耗油量很大的油站，然后将下一个油站作为起点继续判断即可。

Problem

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station"s index if you can travel around the circuit once, otherwise return -1.

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station"s index is 2.

Challenge

O(n) time and O(1) extra space

Note

看到这个题目，怎样可以不把它当成一个环路来分析，以及减少多余的空间呢？
例如gas[i]=[1,1,3,1], cost[i]=[2,2,1,1]，我们引入单次剩余油量res，剩余油量和sum，总剩余油量和total，以及可行起点start四个参数。大体上说，只要total > 0，一定有解。下面来找起点，当sum < 0的时候，一定是上一个加油站的单次剩余油量res为负，且与上一次的剩余油量和sum相加依然为负，说明在上一个加油站出现了消耗大于补给的情况，因此一定不能将它作为起点。所以跳过这个耗油量很大的油站，然后将下一个油站作为起点继续判断即可。

Solution

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0, sum = 0, total = 0;
        for (int i = 0; i < gas.length; i++) {
            int res = gas[i] - cost[i];
            //如果上一次的剩余油量之和sum’加上油站油量gas[i-1]，
            //依然少于上次次的消耗油量cost[i-1]
            if (sum < 0) { 
                //更新出发地点为第i个加油站
                start = i;
                //更新剩余油量之和为到达第i个加油站补给后的剩余油量
                sum = res;
            }
            //否则，将之前的剩余油量之和sum加上本次消耗及补给后的剩余油量res
            else {
                sum += res;
            }
            //累计所有油站的可补给油量和总消耗油量之差（res）
            total += res;
        }
        return total >= 0 ? start : -1;
    }
}

Optimized:

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0, sum = 0, total = 0;
        for (int i = 0; i < gas.length; i++) {
            int res = gas[i] - cost[i];
            sum += res;
            total += res;
            if (sum < 0) {
                sum = 0;
                start = i + 1;
            }
        }
        return total >= 0 ? start : -1;
    }
}

服务器托管私有云 Station GAS gas地图 gas怎么买以太坊

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65660.html

[Leetcode] Gas Station 加油站

摘要：这样我们开始遍历数组，如果是负数，说明开出该加油站后无法到达下一个加油站，这样旅程的起点更新为下一个加油站。 Gas Station There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimi...

lovXin 2019-08-14 12:42 评论0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
[LintCode/LeetCode] Implement Trie

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永刚 2019-08-14 15:23 评论0 收藏0