汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。-天翼云

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

2024-05-09 09:19:54 阅读次数：48

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，每个 station[i] 代表一个加油站，

它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。

它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。

如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]。

输出：2。

具体步骤如下：

1.初始化车内油量 to 和已经加得次数 cnt。

2.遍历所有加油站，对于每个加油站，判断能否到达。如果不能到达，就从大根堆中不断取出油量添加到车内，直至可以到达该加油站或无法再添加油量为止。如果无法到达该加油站，则无法到达目标位置，返回-1。

3.如果能够到达该加油站，则将该加油站的油量添加到大根堆中，并继续向前移动。

4.如果无法到达目标位置，则不断从大根堆中取出油量，直至能够到达目标位置或者大根堆为空为止。

5.返回已经加油的次数。

时间复杂度：O(nlogn)，其中n为加油站的数量。主要是因为该算法使用了堆来维护加油站的油量，每次需要考虑哪个加油站的油量最多，以便优先选择加油量最大的加油站。

空间复杂度：O(n)，其中n为加油站的数量。主要是因为该算法使用了堆存储加油站的油量，所以需要额外的空间存储堆中的元素。

go完整代码如下：

package main

import (
	"container/heap"
)

func minRefuelStops(target int, startFuel int, stations [][]int) int {
	if startFuel >= target {
		return 0
	}

	// 大根堆
	// 维持的是：最值得加油的加油站，有多少油
	// 最值得：加得次数少，跑的还最远
	h := &IntHeap{}
	heap.Init(h)

	// 当前车里的油，能达到的位置
	to := startFuel
	cnt := 0

	for _, station := range stations {
		position := station[0]
		fuel := station[1]

		if to < position {
			for !h.IsEmpty() && to < position {
				to += heap.Pop(h).(int)
				cnt++
				if to >= target {
					return cnt
				}
			}
			if to < position {
				return -1
			}
		}
		heap.Push(h, fuel)
	}

	// 最后一个加油站的位置，都达到了
	// 但还没有到target
	for !h.IsEmpty() {
		to += heap.Pop(h).(int)
		cnt++
		if to >= target {
			return cnt
		}
	}

	return -1
}

func main() {
	target := 100
	startFuel := 10
	stations := [][]int{{10, 60}, {20, 30}, {30, 30}, {60, 40}}
	result := minRefuelStops(target, startFuel, stations)
	println(result)
}

// IntHeap实现大根堆
type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func (h *IntHeap) IsEmpty() bool {
	return h.Len() == 0
}

2023-05-19：汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][

rust完整代码如下：

use std::collections::BinaryHeap;

fn min_refuel_stops(target: i32, start_fuel: i32, stations: Vec<Vec<i32>>) -> i32 {
    if start_fuel >= target {
        return 0;
    }

    // 大根堆
    // 维持的是：最值得加油的加油站，有多少油
    // 最值得：加得次数少，跑的还最远
    let mut heap = BinaryHeap::new();

    // 当前车里的油，能达到的位置
    let mut to = start_fuel as i64;
    let mut cnt = 0;

    for station in stations.iter() {
        let position = station[0] as i64;
        let fuel = station[1] as i64;

        if to < position {
            while !heap.is_empty() && to < position {
                to += heap.pop().unwrap();
                cnt += 1;
                if to >= target as i64 {
                    return cnt;
                }
            }
            if to < position {
                return -1;
            }
        }
        heap.push(fuel);
    }

    // 最后一个加油站的位置，都达到了
    // 但还没有到target
    while !heap.is_empty() {
        to += heap.pop().unwrap();
        cnt += 1;
        if to >= target as i64 {
            return cnt;
        }
    }

    -1
}

fn main() {
    let target = 100;
    let start_fuel = 10;
    let stations = vec![vec![10, 60], vec![20, 30], vec![30, 30], vec![60, 40]];
    let result = min_refuel_stops(target, start_fuel, stations);
    println!("{}", result);
}

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>

// IntHeap实现大根堆，这里用函数指针代替仿函数
int cmp(int a, int b) {
    return a < b;
}

// 交换两个数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

typedef struct IntHeap {
    int (*cmp)(int, int);

    void (*swap)(int*, int*);

    int* data;
    int size;
    int capacity;
}IntHeap;

// 初始化大根堆
void initHeap(IntHeap* heap, int (*cmp)(int, int)) {
    heap->cmp = cmp;
    heap->swap = &swap;
    heap->data = (int*)malloc(sizeof(int) * 128);
    heap->size = 0;
    heap->capacity = 128;
}

// 扩容
void resize(IntHeap* heap) {
    int newCapacity = heap->capacity * 2;
    int* newData = (int*)realloc(heap->data, sizeof(int) * newCapacity);
    heap->data = newData;
    heap->capacity = newCapacity;
}

// 堆化
void down(IntHeap* heap, int i) {
    while (i * 2 + 1 < heap->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int j = left;
        if (right < heap->size && heap->cmp(heap->data[right], heap->data[left])) {
            j = right;
        }
        if (heap->cmp(heap->data[i], heap->data[j])) {
            break;
        }
        heap->swap(&heap->data[i], &heap->data[j]);
        i = j;
    }
}

// 入堆
void pushHeap(IntHeap* heap, int val) {
    if (heap->size == heap->capacity) {
        resize(heap);
    }
    heap->data[heap->size++] = val;

    int i = heap->size - 1;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap->cmp(heap->data[p], heap->data[i])) {
            break;
        }
        heap->swap(&heap->data[p], &heap->data[i]);
        i = p;
    }
}

// 弹出堆顶元素
int popHeap(IntHeap* heap) {
    int top = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    down(heap, 0);
    return top;
}

int minRefuelStops(int target, int startFuel, int** stations, int stationsSize, int* stationsColSize) {
    if (startFuel >= target) {
        return 0;
    }

    // 大根堆
    // 维持的是：最值得加油的加油站，有多少油
    // 最值得：加得次数少，跑的还最远
    IntHeap heap;
    initHeap(&heap, &cmp);

    // 当前车里的油，能达到的位置
    long long to = startFuel;
    int cnt = 0;

    for (int i = 0; i < stationsSize; i++) {
        int position = stations[i][0];
        int fuel = stations[i][1];

        if (to < position) {
            while (heap.size && to < position) {
                to += popHeap(&heap);
                cnt++;
                if (to >= target) {
                    return cnt;
                }
            }
            if (to < position) {
                return -1;
            }
        }
        pushHeap(&heap, fuel);
    }

    // 最后一个加油站的位置，都达到了
    // 但还没有到 target
    while (heap.size) {
        to += popHeap(&heap);
        cnt++;
        if (to >= target) {
            return cnt;
        }
    }

    return -1;
}

int main() {
    int target = 100;
    int startFuel = 10;
    int** stations = (int**)malloc(sizeof(int*) * 4);
    int stationsColSize[4] = { 2, 2, 2, 2 };
    for (int i = 0; i < 4; i++) {
        stations[i] = (int*)malloc(sizeof(int) * 2);
    }
    stations[0][0] = 10;
    stations[0][1] = 60;
    stations[1][0] = 20;
    stations[1][1] = 30;
    stations[2][0] = 30;
    stations[2][1] = 30;
    stations[3][0] = 60;
    stations[3][1] = 40;
    int result = minRefuelStops(target, startFuel, stations, 4, stationsColSize);
    printf("%d\n", result);

    for (int i = 0; i < 4; i++) {
        free(stations[i]);
    }
    free(stations);

    return 0;
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// IntHeap实现大根堆
struct IntHeap {
    bool operator()(int a, int b) { return a < b; }
};

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    if (startFuel >= target) {
        return 0;
    }

    // 大根堆
    // 维持的是：最值得加油的加油站，有多少油
    // 最值得：加得次数少，跑的还最远
    priority_queue<int, vector<int>, IntHeap> heap;

    // 当前车里的油，能达到的位置
    long long to = startFuel;
    int cnt = 0;

    for (auto station : stations) {
        int position = station[0];
        int fuel = station[1];

        if (to < position) {
            while (!heap.empty() && to < position) {
                to += ();
                heap.pop();
                cnt++;
                if (to >= target) {
                    return cnt;
                }
            }
            if (to < position) {
                return -1;
            }
        }
        heap.push(fuel);
    }

    // 最后一个加油站的位置，都达到了
    // 但还没有到target
    while (!heap.empty()) {
        to += ();
        heap.pop();
        cnt++;
        if (to >= target) {
            return cnt;
        }
    }

    return -1;
}

int main() {
    int target = 100;
    int startFuel = 10;
    vector<vector<int>> stations = { {10, 60}, {20, 30}, {30, 30}, {60, 40} };
    int result = minRefuelStops(target, startFuel, stations);
    cout << result << endl;
    return 0;
}

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

具体步骤如下：

go完整代码如下：

rust完整代码如下：

c语言完整代码如下：

c++完整代码如下：

相关文章

C++和C#中数组的比较

图的存储

几种距离度量

Python实战技巧（9）Python发送邮件

R语言文本挖掘tf-idf,主题建模，情感分析,n-gram建模研究|附代码数据

SpringCloud-技术专区-Gateway基于OAuth2.0 的身份认证

Python使用神经网络进行简单文本分类

Python3 - 时间处理与定时任务

QCustomPlot开发笔记（二）：QCustomPlot用户交互、元素项以及特殊用法

用Devc++与easyx一步一步做游戏[启动界面部分]-之按钮制作

作者介绍

最新文章

C++和C#中数组的比较

图的存储

几种距离度量

Python实战技巧（9）Python发送邮件

R语言文本挖掘tf-idf,主题建模，情感分析,n-gram建模研究|附代码数据

SpringCloud-技术专区-Gateway基于OAuth2.0 的身份认证

热门文章

Java学习之算术运算符两只老虎

Lambda函数

R语言方差分析（ANOVA）学生参加辅导课考试成绩差异

r语言中对LASSO，Ridge岭回归和Elastic Net模型实现

通过SAS网络分析对人口迁移进行可视化分析

R语言多分类logistic逻辑回归模型在混合分布模拟个人风险损失值评估的应用

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

Sublime Text自定义代码片段Code Snippets

通过反射的方式调用Java类的方法

求1!+2!+3!+4!+5!+6!+7!+8!+9!+10!+...+N! N阶阶乘求和算法 JAVA C Python（阅读过万）

线性表练习之Example033-将两个按元素值递增次序排列的单链表归并为一个按元素值递减次序排列的单链表

萌妹子Python入门指北（四）

codeforces B. Hungry Sequence