当前位置:   article > 正文

leetcode gas-station(Java)_gas station java

gas station java

leetcode题目

 gas-station
  • 1

题目描述

 * 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.
 * Note: 
 * The solution is guaranteed to be unique.
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

思路

 * 一次遍历法,车能开完全程需要满足两个条件:
 * 1、车从i站能开到i+1。
 * 2、所有站里的油总量要>=车子的总耗油量。
 * 那么,假设从编号为0站开始,一直到k站都正常,在开往k+1站时车子没油了。这时,应该将起点设置为k+1站。
 * 问题1: 为什么应该将起始站点设为k+1?
 * 因为k->k+1站耗油太大,0->k站剩余油量都是不为负的,每减少一站,就少了一些剩余油量。
 * 所以如果从k前面的站点作为起始站,剩余油量不可能冲过k+1站。
 * 
 * 问题2: 为什么如果k+1->end全部可以正常通行,且rest>=0就可以说明车子从k+1站点出发可以开完全程?
 * 因为,起始点将当前路径分为A、B两部分。其中,必然有(1)A部分剩余油量<0。(2)B部分剩余油量>0。
 * 所以,无论多少个站,都可以抽象为两个站点(A、B)。
 * (1)从B站加满油出发,
 * (2)开往A站,车加油,
 * (3)再开回B站的过程。
 * 重点:B剩余的油>=A缺少的总油。必然可以推出,B剩余的油>=A站点的每个子站点缺少的油。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

代码

package com.leetcode.dyncplanning;

/**
 * 
 * 题目描述:
 * 
 * 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.
 * Note: 
 * The solution is guaranteed to be unique.
 * 
 * 中文描述:
 * 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
 * 如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
 * 说明: 
 * 如果题目有解,该答案即为唯一答案。
 * 输入数组均为非空数组,且长度相同。
 * 输入数组中的元素均为非负数。 
 *
 */
public class GasStation {

	/**
	 * 一次遍历法,车能开完全程需要满足两个条件:
	 * 1、车从i站能开到i+1。
	 * 2、所有站里的油总量要>=车子的总耗油量。
	 * 那么,假设从编号为0站开始,一直到k站都正常,在开往k+1站时车子没油了。这时,应该将起点设置为k+1站。
	 * 问题1: 为什么应该将起始站点设为k+1?
	 * 因为k->k+1站耗油太大,0->k站剩余油量都是不为负的,每减少一站,就少了一些剩余油量。所以如果从k前面的站点作为起始站,剩余油量不可能冲过k+1站。
	 * 问题2: 为什么如果k+1->end全部可以正常通行,且rest>=0就可以说明车子从k+1站点出发可以开完全程?
	 * 因为,起始点将当前路径分为A、B两部分。其中,必然有(1)A部分剩余油量<0。(2)B部分剩余油量>0。
	 * 所以,无论多少个站,都可以抽象为两个站点(A、B)。(1)从B站加满油出发,(2)开往A站,车加油,(3)再开回B站的过程。
	 * 重点:B剩余的油>=A缺少的总油。必然可以推出,B剩余的油>=A站点的每个子站点缺少的油。
	 * @param args
	 */
	int canCompleteCircuit(int[] gas, int[] cost) {
	    int rest = 0, run = 0, start = 0;
	    for (int i = 0; i < gas.length; ++i){
	        run += (gas[i] - cost[i]);
	        rest += (gas[i] - cost[i]);
	        if (run < 0){
	            start = i + 1;
	            run = 0;
	        }
	    }
	    return rest < 0 ? -1: start;
	}
	
	public static void main(String[] args) {
		int[] gas = {1,2,3,4,5};
		int[] cost = {3,4,5,1,2};
		System.out.println(new GasStation().canCompleteCircuit(gas, cost));
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

参考:
【leetcode gas station】
【Gas Stattion 解题报告】

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/493503
推荐阅读
相关标签
  

闽ICP备14008679号