[LeetCode] 871. Minimum Number of Refueling Stops @ python

一．题目：
初始油量startFuel，给一个到达目的地所需的油量target，还有沿途的加油站stations(包括到达加油站所需油量以及储备的油量)，求达到目的地所需的最少加油次数，如果到不了返回-1．
二．解题思路：
首先看到最少加油次数，我们会想到从动态规划上解题．这里设dp[i]表示第i次加油之后可以达到的最远距离．每次遍历到第n个加油站时，我们都需要更新dp[1]-dp[n]之间的所有值．
代码如下：

class Solution(object):def minRefuelStops(self, target, startFuel, stations):""":type target: int:type startFuel: int:type stations: List[List[int]]:rtype: int"""#动态规划,设dp[i]表示第i次加油之后可以达到的最远距离dp = [startFuel] + [0] * len(stations) # 初始化dpfor i, (loc, cap) in enumerate(stations): # 遍历加油站for t in range(i, -1, -1):if dp[t] >= loc: # 如果第t次加油后，可以到达 当前加油站的位置。dp[t+1] = max(dp[t+1], dp[t] + cap) # 尝试的更新dpfor i, d in enumerate(dp): # 遍历出最小次数if d >= target: return ireturn -1

其实还有一种更为巧妙的方法，也就是基于贪心的思想．我们记录当前的油量cur，同时把沿途的加油站记录下来放到堆中，知道找到油量不能支持的那个加油站停止，然后在堆中找一个油量最多的加油站，更新当前的油量同时加油次数+1，如果发现堆中没有元素了也就是说明即使我们把沿途的所有加油站的油都算上了，也到不了下一个加油站了．
代码如下：

class Solution(object):def minRefuelStops(self, target, startFuel, stations):""":type target: int:type startFuel: int:type stations: List[List[int]]:rtype: int"""#贪心法steps = 0cur = startFuelheap = []i = 0while True:#如果到达终点了if cur >= target:return steps#把沿途的加油站记录下来 ,找到油量不能支持的前一个加油站while i < len(stations) and cur>=stations[i][0]:heapq.heappush(heap,-stations[i][1])i +=1if not heap:return -1#在没油的时候，选择沿途油量最多的一个加油站加油cur -= heapq.heappop(heap)steps +=1

总结

以上是生活随笔为你收集整理的[LeetCode] 871. Minimum Number of Refueling Stops @ python的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。