leetcode134-加油站

原题

在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。

说明:

  • 如果题目有解,该答案即为唯一答案。
  • 输入数组均为非空数组,且长度相同。
  • 输入数组中的元素均为非负数。

示例1:

输入:
gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。

示例2:

输入:
gas = [2,3,4] cost = [3,4,3] 输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

解法

  1. 解法一:我们从0出发,每经过一个加油站计算剩余的油量(允许负值),那么假设有一个加油站可以从这里出发环行一圈,那么剩余的油量在这之前应该是达到了最低值,后面渐渐才“好起来了”(有起势)。
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int minLeft = Integer.MAX_VALUE;
        int min = -1;
        int gasLeft = 0;
        for(int i = 0;i<gas.length;i++){
            gasLeft += gas[i];
            gasLeft -= cost[i];
            if(gasLeft < minLeft) {
                minLeft = gasLeft;
                min = i;
            }
        }
        int station = min+1==gas.length?0:min+1;
        return gasLeft>=0?station:-1;
    }
}
func canCompleteCircuit(gas []int, cost []int) int {
    gasLeft := 0
    min := math.MaxInt
    minIndex := 0

    for i := 0; i < len(gas); i ++ {
        gasLeft = gasLeft + gas[i] - cost[i]
        if gasLeft < min {
            min = gasLeft
            minIndex = i
        }
    }
    // 从来没有缺过油,那么从第一个开始就行
    if min >= 0 {
        return 0
    }
    // 全程下来油还是不够,则不存在这个解
    if gasLeft < 0{
        return -1
    }
    // 到哪个油站到达了历史低点,则从后面那个油站开始就一定行
    if minIndex == len(gas) -1 {
        return 0
    }
    return minIndex+1
}
  1. 解法二:一次遍历,假如有a b c d e五个加油站,如果从a出发能过b、c,但是过不了d,那么从b出发同样也不能过d;那么只需要从第一个加油站开始检查是否能作为出发点,当遇到过不了的加油站时,直接从下一个加油站开始检查。这样每个加油站最多只需遍历两次,时间复杂度仍是O(n)
func canCompleteCircuit(gas []int, cost []int) int {
    return checkIf(gas, cost, 0, 1)
}

func checkIf(gas []int, cost []int, startIndex int, round int) int {
    if round > 1 && startIndex >= 0{
        return -1
    }
    index := startIndex
    count := 0
    gasLeft := 0
    for count < len(gas){
        gasLeft = gasLeft + gas[index] - cost[index]
        index ++
        count ++
        if index == len(gas){
            index = 0
            round ++
        }
        if gasLeft < 0{
            return checkIf(gas, cost, index, round)
        }
    }
    return startIndex
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode134-%e5%8a%a0%e6%b2%b9%e7%ab%99/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月15日
下一篇 2020年2月16日

相关推荐

  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外…

    算法 2020年5月26日
    0140
  • leetcode599-两个列表的最小索引总和

    原题 假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果…

    算法 2019年12月22日
    0120
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0470
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0150
  • 程序员面试金典17.01-不用加号的加法

    原题(来源Leetcode) 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示: a, b 均可能是负数或…

    算法 2020年6月9日
    0590
  • leetcode238-除自身以外数组的乘积

    原题 给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积…

    算法 2020年6月4日
    0100

发表回复

登录后才能评论