Gas Station leetcode java
2024-10-19 07:36:14
题目:
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.
题解:
网上搜到的解法。
据说是Bloomberg的面试题。
用两个变量存+= gas[i] - cost[i]。一个帮助判断当前这个点作为gas station的起点合不合适,一个帮助判断总的需求是不是大于供给。如果总的需求大于供给那么肯定是无解的,如果需求小于等于供给,就可以返回刚才找到的起始点。
代码如下:
1 public int canCompleteCircuit(int[] gas, int[] cost) {
2 if (gas==null|| cost==null||gas.length==0||cost.length==0||gas.length!=cost.length)
3 return -1;
4
5 int sum = 0;
6 int total = 0;
7 int index = 0;
8 for(int i = 0; i < gas.length; i++){
9 sum += gas[i]-cost[i];
total += gas[i]-cost[i];
if(sum < 0){
index=i+1;
sum = 0;
}
}
if(total<0)
return -1;
else
return index;
}
Reference:http://blog.csdn.net/lbyxiafei/article/details/12183461
最新文章
- C# Memcache分布式缓存简单入门
- 解决windows 2003 无法安装vss2005的问题
- 1282 - Leading and Trailing ---LightOj1282(快速幂 + 数学)
- 从问题看本质:socket到底是什么(问答式)? .
- 总结c++ primer中的notes
- Mac环境下装node.js,npm,express;(包括express command not found)
- bzoj4028
- GIT 版本控制命令学习
- Ubuntu火狐、Chromium等浏览器安装flash插件
- Git合并分支出现的冲突解决
- ios 视频拼接/合成
- Spring boot——logback 基础使用篇(一)
- VS2015企业版和专业版永久密匙
- Android自定义View(三、深入解析控件测量onMeasure)
- json.parseArray源码解析
- Python-Django学习
- java学习笔记(十):scanner输入
- Java 实现字符串的加密与解密
- uigetfile的用法(批量读取图片)
- jsp+Servlet+JavaBean+JDBC+MySQL项目增删改查