`
blue2048
  • 浏览: 186267 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Gas Station - java

阅读更多

两种解法

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题解之Gas Station.java

    Java程序员在准备算法面试或提升算法能力时,经常会参考LeetCode平台上的编程题目进行练习。Gas Station这一题目属于典型的算法问题,主要考察对数组操作、贪心算法的理解和应用。解决这个问题需要思考如何在只遍历...

    gasstationleetcode-leetcode-java:leetcode-java

    - GasStation.java: "加油站"问题的Java实现 - OtherProblems/ - Problem1.java: 其他问题的Java实现 - Problem2.java - ... - tests/ - GasStationTest.java: 对"加油站"问题的测试用例 - ...

    Leetcode题目+解析+思路+答案.pdf

    - **Gas Station**:寻找最短的加油路线。 - **Candy**:分糖果,确保每个孩子至少得到一块糖,尽可能公平。 - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List...

    gasstationleetcode-leetcode:我对leetcode问题的解决方案

    gas station leetcode leetcode # Title README Java Python 0002 0003 0005 0010 0011 0015 0019 0022 0023 0046 0050 0054 0064 0070 0079 0079 0084 0098 0102 0103 0104 README 0110 0110 0124 0125 0134 0142 ...

    gasstationleetcode-LeetCode:Leetcode问题解决方案

    在LeetCode平台上,题目“Gas Station”是一道著名的算法问题,属于中等难度。这个问题旨在测试程序员对于数组处理、线性搜索以及优化算法的理解。在这个压缩包文件"gasstationleetcode-LeetCode:LeetCode问题解决...

    leetcode c++程序

    11. LeetCode题目案例:文档中提到了一些特定的LeetCode题目案例,如SetMatrixZeroes、GasStation、Candy、SingleNumber等。这些案例覆盖了数组、单链表、字符串等数据结构的多种操作,体现了各种算法应用场景。 12...

    gasstationleetcode-LeetCodeCPP:算法练习

    gas station leetcode LeetCodeCPP 题目来自于牛客网在线编程模块leetcode经典编程题, 激励自己进行算法练习。 148道LeetCode数据结构算法经典在线编程题C++、Java实现 、C++版本:

    gasstationleetcode-Circular-Petrol-Pump-Problem:循环汽油泵问题

    在LeetCode平台上,"Gas Station"(加油站)问题是一个经典的算法题目,被命名为"Circular Petrol Pump Problem"(循环汽油泵问题)。这个问题涉及到图论、数学和贪心算法,是解决实际生活中的路线规划问题的一个...

Global site tag (gtag.js) - Google Analytics