python - 贪心算法的汽车加油问题(列表索引超出范围)

Question

我有一个使用贪婪算法解决汽车加油问题的小问题。

问题介绍

You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1 stop2 . . . ,stopN from your home city. What is the minimum number of refills needed?

输入:

950
400
4
200 375 550 750

输出:

2

到目前为止我尝试过的

def car_fueling(dist,miles,n,gas_stations):
  num_refill, curr_refill, last_refill = 0,0,0
  while curr_refill <= n:
    last_refill = curr_refill
    while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    if curr_refill == last_refill:  
      return -1
    if curr_refill <= n:
      num_refill += 1
  return num_refill

我面临的问题是什么

在声明中

while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles)

我收到错误 IndexError: list index out of range .是因为 gas_stations[curr_refill + 1] .因此，当我尝试将其分隔为 while 时循环和 if声明如

while (curr_refill <= n-1):
    if (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    else:
        break

它正在进入一个无限循环。

你能指出我面临的错误吗？

提前致谢。

Answer 1

几个问题:

&不是 bool 和运算符。使用 and

curr_refill + 1可以 n ，从而产生你得到的错误。请注意，最后一个加油站后的距离可以使用 dist 确定。

last_refill的值从一开始就是错误的:您(还)没有在 0 号站重新填充，因此不应将其初始化为 0。而是使用另一个代表您当前可以行驶多远的变量。

更正的代码:

def car_fueling(dist,miles,n,gas_stations):
    num_refill, curr_refill, limit = 0,0,miles
    while limit < dist:  # While the destination cannot be reached with current fuel
        if curr_refill >= n or gas_stations[curr_refill] > limit:
            # Cannot reach the destination nor the next gas station
            return -1
        # Find the furthest gas station we can reach
        while curr_refill < n-1 and gas_stations[curr_refill+1] <= limit:
            curr_refill += 1
        num_refill += 1  # Stop to tank
        limit = gas_stations[curr_refill] + miles  # Fill up the tank 
        curr_refill += 1
    return num_refill

# Test cases
print(car_fueling(950, 400, 4, [200, 375, 550, 750]))  # 2
print(car_fueling(10, 3, 4, [1, 2, 5, 9]))  # -1