两种解法
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 java_leetcode-115-distinct-subsquences
java java_leetcode-101-symmetric-tree
java java_leetcode-100-same-tree
java java_leetcode-112-path-sum
java java_leetcode-73-set-matrix-zeroes
java java_leetcode-110-balanced-binary-tree
java java_leetcode-113-path-sumII
java java_leetcode-maximum-depth-of-binary-tree
java java_leetcode-99-recover-binary-search-tree
java java_leetcode-111-minimum-depth-of-binary-tree
java java_leetcode-107-binary-tree-level-order-traversal
java java_leetcode-102-binary-tree-level-order-traversal
java java_leetcode-114-flatten-binary-tree-to-linked-list
java java_leetcode-105-construct-binary-tree-from-preorder-and-inorde
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
本资源“javalruleetcode-leetcode-algorithms-java”专注于 Java 语言在 LeetCode 平台上的算法实现,特别提到了 LRUCache(最近最少使用)数据结构,这是解决实际编程问题时常用的一种高效策略。 LRUCache 是一种...
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
《LeetCode-Java-Solutions: Java中LeetCode在线判断问题的解决方案详解》 在编程学习与进阶的过程中,LeetCode是一个不可多得的资源库,它提供了大量的算法题目供程序员练习,以提升自身的编程能力和算法水平。...
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
《LeetCode-Index-master》是针对LeetCode在线编程平台的一个资源包,主要目的是为了帮助用户更好地理解和解决LeetCode上的算法问题。LeetCode是一个广受欢迎的在线编程挑战平台,它提供了大量的算法题目,帮助...