Gas Station——LeetCode

时间:2022-09-21 09:30:39

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个加油站围成一个圈,每个加油站的油量是gas[i],从第i个加油站开到第i+1个加油站需要耗费cost[i]油量,问是否有一个解使得从某个加油站开始跑一圈,有的话返回开始跑的加油站的index。

我的做法就是从0开始遍历,sum+=gas[i]-cost[i],一旦sum<0了,说明从当前到0的所有点都不可能了,然后从下一个开始,一旦跑完一圈发现sum都不小于0,那么就可以返回当前的index了,否则全部遍历一遍没有解就返回-1。

Talk is cheap>>

  public int canCompleteCircuit(int[] gas, int[] cost) {
int res;
for (int i = 0; i < gas.length; i++) {
res = gas[i] - cost[i];
if (res >= 0) {
int pos = i;
for (int j = pos + 1; j < gas.length + pos; j++) {
int index = j % gas.length;
res += gas[index] - cost[index];
if (res < 0) {
pos = -1;
i = j;
break;
}
}
if (pos >= 0)
return pos;
}
}
return -1;
}

Gas Station——LeetCode的更多相关文章

  1. 134&period; Gas Station leetcode

    134. Gas Station 不会做. 1. 朴素的想法,就是针对每个位置判断一下,然后返回合法的位置,复杂度O(n^2),显然会超时. 把这道题转化一下吧,求哪些加油站不能走完一圈回到自己,要求 ...

  2. Gas Station &lbrack;LeetCode&rsqb;

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

  3. Gas Station leetcode java

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

  4. Gas Station&vert;leetcode 贪心

    贪心:尽量将gas[i]-cost[i]>0的放在前面,gas[i]-cost[i]<0的放在后面.(路程的前面有汽油剩下,耗汽油的放在路程的后面). 能否全程通过的 条件 是:sum(g ...

  5. Gas Station &lbrack;leetcode&rsqb; 两个解决方案

    因为gas的总数大于cost总时间.你将能够圈住整个城市. 第一溶液: 如果一開始有足够的油.从位置i出发.到位置k时剩余的油量为L(i,k). 对随意的k.L(i,k)依据i的不同,仅仅相差常数. ...

  6. &lbrack;LeetCode&rsqb; Gas Station 加油站问题

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

  7. &lbrack;LeetCode&rsqb; Gas Station

    Recording my thought on the go might be fun when I check back later, so this kinda blog has no inten ...

  8. leetcode&commat; &lbrack;134&rsqb; Gas station &lpar;Dynamic Programming&rpar;

    https://leetcode.com/problems/gas-station/ 题目: There are N gas stations along a circular route, wher ...

  9. &lbrack;LeetCode&rsqb; 134&period; Gas Station 解题思路

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

随机推荐

  1. 转--webservice、socket、http 小记(一)

    webservice.socket.http 小记(一) http://blog.csdn.net/m_123hj_520/article/details/9370723 2013-07-18 17: ...

  2. ZOJ Problem Set - 3643 Keep Deleting

    题目大意: 给出a和b串,a是b串的子串,如果b串有连续的a串,那么就将b串的a串删除,问删除多少次: 题目分析: 打比赛的时候没敲出来,后来想到用栈的思想去模拟就行,网上还有用KMP+栈去做的,没有 ...

  3. Android ListView(Selector 背景图片 全选 Checkbox等按钮)

    list_item.xml <?xml version="1.0" encoding="utf-8"?> <RelativeLayout xm ...

  4. &lbrack;Python&rsqb;更加Pythonic的多个List合并和Python的安利

    原题: https://segmentfault.com/q/1010000005904259 问题: 倘若存在 L=[ [1,2,3],[4,5,6],[7,8,9]] 这样的列表,如何把合并成[1 ...

  5. Linq101-CustomSequence

    using System; using System.Collections.Generic; using System.Linq; namespace Linq101 { class CustomS ...

  6. c&sol;c&plus;&plus;与java------之JNI学习(一)

    一.java 调用c/c++ 步骤: 1.在java类中创建一个native关键字声明的函数 2.使用javah生成对应的.h文件 3.在c/c++中实现对应的方法 4.使用vs2012创建一个win ...

  7. QuietHit小Game

    根据项目的要求分别建出几个类 有游戏类 玩家类 测试类 等级类 等级时间类 一以下类图: 游戏类: public class Game { private Player player; public ...

  8. &vert; dp-the Treasure Hunter

    题目: A. Mr. Kitayuta, the Treasure Hunter time limit per test 1 second memory limit per test 256 mega ...

  9. 机器学习随笔01 - k近邻算法

    算法名称: k近邻算法 (kNN: k-Nearest Neighbor) 问题提出: 根据已有对象的归类数据,给新对象(事物)归类. 核心思想: 将对象分解为特征,因为对象的特征决定了事对象的分类. ...

  10. Python 3&period;x 格式化输出字符串 &percnt; &amp&semi; format 笔记

    Python 3.x 格式化输出字符串 % & format 笔记 python格式化字符串有%和{}两种 字符串格式控制符. 字符串输入数据格式类型(%格式操作符号) %%百分号标记 %c字 ...