贪婪算法的汽车加油问题（获取列表索引超出范围）
Car Fueling Problem by Greedy Alogorithm (getting list index out of range)
我在使用贪心算法解决汽车加油问题时遇到了一个小问题。
问题介绍
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
正在进入死循环。
你能指出我面临的错误吗？
提前致谢。
这是一个无限循环，因为 n 没有递增。
在最有意义的地方增加 n（例如，在 while 语句的末尾）。
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
n+=1 # Increment
return num_refill
几个问题：
& 不是布尔运算符。使用 andcurr_refill + 1 可以是 n，因此会产生您遇到的错误。请注意，可以使用 distlast_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
def car_refill(dist,cap,n,stops):
stops.insert(0,0)
stops.append(dist)
num_refill,curr_refill = 0,0
while curr_refill <= n:
last_refill = curr_refill
while (curr_refill <= n and stops[curr_refill + 1] - stops[last_refill] <= cap):
curr_refill += 1
if curr_refill == num_refill :
return -1
if curr_refill <= n:
num_refill +=1
return num_refill
试试这个....
我不知道为什么，但答案似乎过于复杂，我只是想象自己在开车，想出了这个简单的解决方案
function minfill(distance, miles, n, stations) {
//added final distance to last station for simplicity can simply push to array.
stations = [...stations, distance]
let refill = 0,
limit = miles,
dt = 0, //distance travelled
current = 0; //current station
while (current <= n) {
//check if next or first station is unreachable
if ((Math.abs(stations[current] - stations[current + 1]) > limit) || stations[0] > limit) return -1
//check if we need to refuel or pass
if (Math.abs(dt - stations[current]) <= limit) {
current++
}
//if next distance was over limit we set distance tavelled to previous station ,current station was already pointed to next in above block
else {
dt = stations[current - 1]
refill++
}
}
return refill
}
p.s-this 代码是用 node/javascript 编写的，虽然我已经通过了这个问题的所有测试，但我知道这里有更聪明的人会帮助 improve/correct 这个代码或者提供一些指点。
这可能会修复索引错误。您的代码逻辑是正确的，这与我在 else 语句块中的代码中所做的相同。添加起点和终点（总距离）可以避免索引错误。首先查看总距离，看是否可以满罐到达。如果不执行 else 语句。
def compute_min_refills(distance, tank, stops):
numrefill, currentrefill= 0,0
stops = [0] + stops + [distance] #include the start and end points in the stops list
if distance <= tank:
return 0
else:
while currentrefill < len(stops)-1:
lastrefill = currentrefill
#print(currentrefill, lastrefill, len(stops))
while currentrefill < len(stops)-1 and stops[currentrefill+1] - stops[lastrefill]<=tank:
currentrefill += 1
if currentrefill == lastrefill:
return -1
if currentrefill < len(stops)-1:
numrefill +=1
#print(numrefill)
return numrefill
if __name__ == '__main__':
#print(compute_min_refills(10, 3, [1,2,5,9]))
导入java.util.；
导入 java.io.;
public class 汽车加油 {
static int compute_refills(int dist, int tank, int stops[], int n) {
int current_refills=0;
int num_refills=0;
int last_refill=0;
while(current_refills<=n) {
last_refill = current_refills;
while ((current_refills !=stops.length-1) && (stops[current_refills + 1] - stops[last_refill]) <= tank) {
current_refills +=1 ;
}
if (current_refills == last_refill)
return -1;
if (current_refills <= n)
num_refills +=1;
}
return num_refills;
}
public static void main (String[]args){
Scanner scanner = new Scanner(System.in);
int dist = scanner.nextInt();
int tank = scanner.nextInt();
int n = scanner.nextInt();
int stops[] = new int[n * n * n];// to solve array index out of bound exception increase the size of the array
for (int i = 0; i < n; i++) {
stops[i] = scanner.nextInt();
}
System.out.println(compute_refills(dist, tank, stops, n));
}
}
将 [0] 和 [d] 添加到停靠点的答案应该有效，但是 current_refill 比较应该到处都是 current_refill < len(stops)- 2，因为添加了两个停靠点。
还有另一种方法可以解决这个问题。
def compute_min_number_of_refills(d, m, stops):
if d <= m:
return 0
total_refill = 0
last_refill = -1
limit = m
stops.append(d)
i = 0
while i < len(stops):
if stops[i] >= limit:
current_refill = i - 1 if stops[i] > limit else i
if current_refill == last_refill:
return -1
last_refill = current_refill
total_refill += 1
limit = m + stops[current_refill]
i = current_refill + 1
else:
i += 1
return total_refill
我使用了这段代码，并从 Coursera 的一门课程中得到了正确答案。
# python3
import sys
def compute_min_refills(distance, tank, stops):
capacity_tank = tank
refill = 0
if capacity_tank >= distance:
return 0
if capacity_tank < stops[0] or (distance-stops[-1]) > capacity_tank:
return -1
for i in range(1, len(stops)):
if (stops[i]-stops[i-1]) > capacity_tank:
return -1
if stops[i] > tank:
tank = (stops[i-1] + capacity_tank)
refill += 1
if distance > tank:
refill += 1
return refill
if __name__ == '__main__':
d, m, _, *stops = map(int, sys.stdin.read().split())
print(compute_min_refills(d, m, stops))
我在使用贪心算法解决汽车加油问题时遇到了一个小问题。
问题介绍
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
正在进入死循环。
你能指出我面临的错误吗？
提前致谢。
这是一个无限循环，因为 n 没有递增。
在最有意义的地方增加 n（例如，在 while 语句的末尾）。
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
n+=1 # Increment
return num_refill
几个问题：
&不是布尔运算符。使用andcurr_refill + 1可以是n，因此会产生您遇到的错误。请注意，可以使用dist 确定 last 加油站之后的距离
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
def car_refill(dist,cap,n,stops):
stops.insert(0,0)
stops.append(dist)
num_refill,curr_refill = 0,0
while curr_refill <= n:
last_refill = curr_refill
while (curr_refill <= n and stops[curr_refill + 1] - stops[last_refill] <= cap):
curr_refill += 1
if curr_refill == num_refill :
return -1
if curr_refill <= n:
num_refill +=1
return num_refill
试试这个....
我不知道为什么，但答案似乎过于复杂，我只是想象自己在开车，想出了这个简单的解决方案
function minfill(distance, miles, n, stations) {
//added final distance to last station for simplicity can simply push to array.
stations = [...stations, distance]
let refill = 0,
limit = miles,
dt = 0, //distance travelled
current = 0; //current station
while (current <= n) {
//check if next or first station is unreachable
if ((Math.abs(stations[current] - stations[current + 1]) > limit) || stations[0] > limit) return -1
//check if we need to refuel or pass
if (Math.abs(dt - stations[current]) <= limit) {
current++
}
//if next distance was over limit we set distance tavelled to previous station ,current station was already pointed to next in above block
else {
dt = stations[current - 1]
refill++
}
}
return refill
}
p.s-this 代码是用 node/javascript 编写的，虽然我已经通过了这个问题的所有测试，但我知道这里有更聪明的人会帮助 improve/correct 这个代码或者提供一些指点。
这可能会修复索引错误。您的代码逻辑是正确的，这与我在 else 语句块中的代码中所做的相同。添加起点和终点（总距离）可以避免索引错误。首先查看总距离，看是否可以满罐到达。如果不执行 else 语句。
def compute_min_refills(distance, tank, stops):
numrefill, currentrefill= 0,0
stops = [0] + stops + [distance] #include the start and end points in the stops list
if distance <= tank:
return 0
else:
while currentrefill < len(stops)-1:
lastrefill = currentrefill
#print(currentrefill, lastrefill, len(stops))
while currentrefill < len(stops)-1 and stops[currentrefill+1] - stops[lastrefill]<=tank:
currentrefill += 1
if currentrefill == lastrefill:
return -1
if currentrefill < len(stops)-1:
numrefill +=1
#print(numrefill)
return numrefill
if __name__ == '__main__':
#print(compute_min_refills(10, 3, [1,2,5,9]))
导入java.util.； 导入 java.io.;
public class 汽车加油 {
static int compute_refills(int dist, int tank, int stops[], int n) {
int current_refills=0;
int num_refills=0;
int last_refill=0;
while(current_refills<=n) {
last_refill = current_refills;
while ((current_refills !=stops.length-1) && (stops[current_refills + 1] - stops[last_refill]) <= tank) {
current_refills +=1 ;
}
if (current_refills == last_refill)
return -1;
if (current_refills <= n)
num_refills +=1;
}
return num_refills;
}
public static void main (String[]args){
Scanner scanner = new Scanner(System.in);
int dist = scanner.nextInt();
int tank = scanner.nextInt();
int n = scanner.nextInt();
int stops[] = new int[n * n * n];// to solve array index out of bound exception increase the size of the array
for (int i = 0; i < n; i++) {
stops[i] = scanner.nextInt();
}
System.out.println(compute_refills(dist, tank, stops, n));
}
}
将 [0] 和 [d] 添加到停靠点的答案应该有效，但是 current_refill 比较应该到处都是 current_refill < len(stops)- 2，因为添加了两个停靠点。
还有另一种方法可以解决这个问题。
def compute_min_number_of_refills(d, m, stops):
if d <= m:
return 0
total_refill = 0
last_refill = -1
limit = m
stops.append(d)
i = 0
while i < len(stops):
if stops[i] >= limit:
current_refill = i - 1 if stops[i] > limit else i
if current_refill == last_refill:
return -1
last_refill = current_refill
total_refill += 1
limit = m + stops[current_refill]
i = current_refill + 1
else:
i += 1
return total_refill
我使用了这段代码，并从 Coursera 的一门课程中得到了正确答案。
# python3
import sys
def compute_min_refills(distance, tank, stops):
capacity_tank = tank
refill = 0
if capacity_tank >= distance:
return 0
if capacity_tank < stops[0] or (distance-stops[-1]) > capacity_tank:
return -1
for i in range(1, len(stops)):
if (stops[i]-stops[i-1]) > capacity_tank:
return -1
if stops[i] > tank:
tank = (stops[i-1] + capacity_tank)
refill += 1
if distance > tank:
refill += 1
return refill
if __name__ == '__main__':
d, m, _, *stops = map(int, sys.stdin.read().split())
print(compute_min_refills(d, m, stops))