[LeetCode] 134. 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 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. 【解释】 给定两个数组,gas[i]表示第i个站点的天然气容量,cost[i]表示从第i个站点到下一个站点所需要的天然气数量,假设车子天然气容量无限制(即可以将一个站点的所有天然气加完)。问从哪个站点开始可以环游所有站点一圈。 【思路】 暴力解法,从每一个站点开始看能不能到达所有站点。复杂度为O(n2)O(n^2), TLE。

思路一 试想如果所有的gas值加起来都没有cost数组大,那么无论怎么走最后肯定是不可达。但是在前者的和不比后者小的时候应该从哪里开始走呢,可以肯定的是可行的路径中间是不可能出现gas-cost的差和小于零的情况。 举个栗子, 假设:

int[] gas={1,2,3,3}
int[] cost={2,1,4,1}

差和数组differ为{-1,1,-2,2} 第零个差和数组元素为-1,肯定不可能从这里开始 从第一个差和数组元素开始,到最后都不小于零,则返回1; 可能有人会有疑问,为什么?? 试想我们已经保证差和已经是不小于零了,那么必然就存在一条路径,且目前已经排除了从前面站点开始的路径,假设当前站点为cur(例子中为1),假设后面的站点存在从post站点(例子中为3)开始的和也不小于零,那么我们返回cur站点也是对的,这样也刚好满足的题目的要求。

public class Solution {
  public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas.length==0) return -1;
        int[] differ=new int[gas.length];
        for(int i=0;i<gas.length;i++)
            differ[i]=gas[i]-cost[i];
        int startIndex=-1;
        int sum=0;//统计所有的差和
        int tmpSum=0;//统计第一个差不小于零的路径和
        for(int i=0;i<differ.length;i++){
            sum+=differ[i];
            tmpSum+=differ[i];
            if(tmpSum<0){//如果小于零则重置
                startIndex=i;
                tmpSum=0;
            }
        }
        if(sum<0) return -1;
        else 
        return startIndex+1;//从不满足要求的下一个站点开始
}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏飞扬的花生

文件方法

C# 获取指定目录下所有文件信息、移动目录、拷贝目录 /// <summary> /// 获取目录下的所有文件夹和文件的path ...

1775
来自专栏HansBug's Lab

3297: [USACO2011 Open]forgot

3297: [USACO2011 Open]forgot Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 69...

2476
来自专栏乐享123

Udp Packet Receive Errors

2265
来自专栏乐沙弥的世界

WSREP has not yet prepared node for application use

最近PXC 5.7出现脑裂,前端Navicate连接到MySQL时,提示WSREP has not yet prepared node for applicat...

793
来自专栏iOS 开发杂谈

HTTPS 之对称加密与非对称加密

加密 encryption 与解密 decryption 使用的是同样的密钥 secret key,对称加密是最快速、最简单的一种加密方式。加密和解密算法是公开...

774
来自专栏小工匠技术圈

【Java小工匠聊密码学】--非对称加密--概述

  非对称加密算法需要两个密钥:[公开密钥] (publickey)和私有密钥(privatekey)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,...

743
来自专栏Java后端技术

C#实现把指定文件夹下的所有文件复制到指定路径下以及修改指定文件的后缀名

731
来自专栏用户画像

第21章 DHCP

1.在TCP/IP协议族中,应用层的各种服务是建立在传输层提供服务的基础上,下列哪组协议需要使用传输层的TCP建立连接()。

572
来自专栏吴伟祥

加密 原

在日常设计及开发中,为确保数据传输和数据存储的安全,可通过特定的算法,将数据明文加密成复杂的密文。目前主流加密手段大致可分为单向加密和双向加密。

563
来自专栏小樱的经验随笔

Codeforces 716A Crazy Computer

A. Crazy Computer time limit per test:2 seconds memory limit per test:256 megaby...

35010

扫码关注云+社区