LeetCode刷题——加油站#134#Medium

加油站的思路探讨与源码
    加油站的题目如下图,该题属于贪心和搜索类型的题目,主要考察对于搜索方法的使用和该问题直接遍历的理解。本文的题目作者想到2种方法,分别是贪心方法和双指针方法,其中贪心方法使用Java进行编写,而双指针方法使用Python进行编写,当然这可能不是最优的解法,还希望各位大佬给出更快的算法。
LeetCode刷题——加油站#134#Medium_第1张图片
    本人认为该题目可以使贪心算法进行解决,首先初始化参数并求得数组长度,开始遍历搜索数组,在循环内部也进行油量和成本所需数值的参数初始化,开始在循环内进行遍历,遵循的思想是假设有两个站点A和B,如果A到不了B+1,但A可以到B,那么从A到B的任一点出发都不可能到达B+1,相当于这就是终止搜索的一个条件,防止超过时间限制,在循环的后面求出了油量和成本后进行判断,如果消耗量大于油量就终止遍历搜索并跳出,然后判断当前下标和数组长度是否一样,如果是就返回最后的位置,否则就继续将初始下标更新到遍历的下一个位置。如果到最后还是没有搜索到,就返回-1的结果。那么按照这个思路我们的Java代码如下:

#喷火龙与水箭龟
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int jr = 0;
        int gasLen = gas.length;
        while (jr < gasLen) {
            int gasSumNum = 0;
            int paySumNum = 0;
            int num = 0;
            while(numgasSumNum){
                    break;
                }
                num = num + 1;
            }
            if(num==gasLen){
                return jr;
            } else {
                jr = jr + num + 1;
            }
        }
        return -1;
    }
}

LeetCode刷题——加油站#134#Medium_第2张图片
    显然,我们看到贪心算法的效果还行,同时还可以使用双指针的方法解决。首先是进行参数初始化,计算数组长度并将第一个元素的值进行记录,开始遍历循环,如果油不够开到下一个节点,那么将当前位置的前一位设置为初始值,并且把消耗的油加上去;如果油的够的,那么就把消耗的油减去,然后去到下一个节点,并把下一个节点的油加入进来。最后循环结束再判断一下终点的油是否可以开到起点,如果可以就返回出发的起始位置,否则就返回-1的结果。所以按照这个思路就可以解决,下面是Python代码:

#喷火龙与水箭龟
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        gasLen = len(gas)
        begin = 0
        crx = 0
        gasNum = gas[0]
        while((crx + 1) % gasLen != begin):
            if(gasNum < cost[crx]):
                begin = (begin - 1) % gasLen
                gasNum = gasNum + gas[begin] - cost[begin]
            else:
                gasNum = gasNum - cost[crx]
                crx = (crx + 1) % gasLen
                gasNum = gasNum + gas[crx]
        if(gasNum - cost[crx] >= 0):
            return begin
        else:
            return -1

LeetCode刷题——加油站#134#Medium_第3张图片
    从结果来说Java版本的贪心方法的效率还可以,而Python版本的双指针方法的速度一般,但应该是有更多的方法可以进一步提速的,希望朋友们能够多多指教,非常感谢。

你可能感兴趣的