贪心算法的汽车加油问题（列表索引超出范围）

Question

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

问题介绍

您将前往距离您家乡数英里的另一个城市。您的汽车在加满油箱的情况下最多可以行驶数英里，而您从加满油箱开始。沿途有加油站，距离 stop1 stop2 。. . ,stopN 从你的家乡城市。最少需要多少次补充？

输入：

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

几个问题：

• &不是布尔和运算符。用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