两种解法
1. 两层遍历,直观取得结果 --- 时间复杂度高 ,不过, 但如果要求返回所有满足的位置,可以用这种方法
2. 题目只要求返回一个结果即可,那么有以下两个条件,即满足题意
a. ∑gas[i] >= ∑cost[i]
b. 从cost[i]-gas[i]的负数最小的地方,往后找到第一个cost[i]-gas[i]>0的index,则此位置即满足要求
第一种解法,(time limit exceeded)
public int canCompleteCircuitFailed(int[] gas, int[] cost) { if(gas == null || gas.length==0){ return -1; } for(int i=0; i<gas.length; i++){ if(cost[i]>gas[i]){ continue; } int totalGas =0 ; int totalCost =0 ; int j=i; boolean circuitFlag = true; while (true){ if(j == i && circuitFlag){ circuitFlag = false; }else if(j==i && !circuitFlag ){ return i; } totalCost += cost[j]; totalGas += gas[j]; if(totalCost > totalGas){ break; } if((j+1)==gas.length){ j = 0; }else { j++; } } continue; } return -1; }
第二种
public int canCompleteCircuit(int[] gas, int[] cost) { int gasCostMin = 0; int gasMinIndex = -1; int totalGas = 0; int totalCost = 0; for(int i=0; i<gas.length; i++){ if((gas[i]-cost[i]) < gasCostMin){ gasCostMin = gas[i]-cost[i]; gasMinIndex = i; } totalCost += cost[i]; totalGas += gas[i]; } if(totalGas >= totalCost){ if(gasMinIndex == -1){ return 0; } int j = gasMinIndex; while (true){ if(gas[j]-cost[j]>0){ return j; } j++; if(j==gas.length){ j=0; } } } return -1; }
相关推荐
力扣解题java版本
leetcode 答案解析 golang解答
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
用Java实现基础数据结构,排序算法、经典算法以及leetcode刷题记录_Java_下载.zip
java lru leetcode leetcode-algorithms-java leetcode 算法笔记-java
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
leetcode-helper-1.7.1
leetcode Leetcode-Java-解决方案 Java 中 Leetcode 问题的解决方案
leetcode-tag-dynamic programming
LeetCode-Python-Java zhouzhenping/LeetCode-Python&Java 参考代码来源 力扣(LeetCode) 链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 Github 01 两数之和 给定一个整数数组 ...
#Leetcode-In-Java 代码并不全是本人写的,有的参考了网络上其他前辈的想法,但都能在OJ上AC。 ###索引 1 . Two-Sum 要点: - 利用java中Array对象的sort方法排序,使得整个数组呈升序状态 - 再利用两段取点...
分类LeetCode-Java-接受 这是 Leetcode 问题的 Java 解决方案。 细节 标题和答案格式 /* * 17. Letter Combinations of a Phone Number * Target: Given a string containing digits from 2-9 inclusive, return all...
leetcode 答案LeetCode-答案-Java 我的 leetcode 用伪代码和分析用 java 回答
leetcode-tag-Stack
leetcode-tag-array
LeetCode题解 - Java语言实现-181页.pdf
然后通过用循环来解:假设第一个for循环是一个数组的循环,而后它的内嵌循环是也是这个数组,只是下标从0变成了1,这样,在第一次循环时,第1个元素会与其他所有元素
LeetCode-Practice-Java leetcode 练习题 这个项目就是自己练习leetCode的实际Demo 有些公司就会问一些算法问题,即便是不问的话自己不学这块感觉也对不起自己的职业。。。 所以自己在学习的时候 也打算把优秀的答案...
leetcode-for-Java Record the process of leetcode for Java. 引言 记录一下,在leetcode上刷题的过程。 前期以刷题为主。有空的话就更新一下这个目录,然后顺带把有写问题的解题思路写上。 目录
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案