2023-05-19：汽車從起點出發(fā)駛向目的地，該目的地位于出發(fā)位置東面 target 英里處。
2023-05-19：汽車從起點出發(fā)駛向目的地，該目的地位于出發(fā)位置東面 target 英里處。
沿途有加油站，每個 station[i] 代表一個加油站，
它位于出發(fā)位置東面 station[i][0] 英里處，并且有 station[i][1] 升汽油。
假設汽車油箱的容量是無限的，其中最初有 startFuel 升燃料。
它每行駛 1 英里就會用掉 1 升汽油。
當汽車到達加油站時，它可能停下來加油，將所有汽油從加油站轉移到汽車中。
為了到達目的地，汽車所必要的最低加油次數(shù)是多少？如果無法到達目的地，則返回 -1 。
注意：如果汽車到達加油站時剩余燃料為 0，它仍然可以在那里加油。
如果汽車到達目的地時剩余燃料為 0，仍然認為它已經(jīng)到達目的地。
輸入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]。
輸出：2。
答案2023-05-19：
具體步驟如下：
1.初始化車內油量 to 和已經(jīng)加得次數(shù) cnt。
2.遍歷所有加油站，對于每個加油站，判斷能否到達。如果不能到達，就從大根堆中不斷取出油量添加到車內，直至可以到達該加油站或無法再添加油量為止。如果無法到達該加油站，則無法到達目標位置，返回-1。
3.如果能夠到達該加油站，則將該加油站的油量添加到大根堆中，并繼續(xù)向前移動。
4.如果無法到達目標位置，則不斷從大根堆中取出油量，直至能夠到達目標位置或者大根堆為空為止。
5.返回已經(jīng)加油的次數(shù)。
時間復雜度：O(nlogn)，其中n為加油站的數(shù)量。主要是因為該算法使用了堆來維護加油站的油量，每次需要考慮哪個加油站的油量最多，以便優(yōu)先選擇加油量最大的加油站。
空間復雜度：O(n)，其中n為加油站的數(shù)量。主要是因為該算法使用了堆存儲加油站的油量，所以需要額外的空間存儲堆中的元素。
go完整代碼如下：
package?main
import?(
????"container/heap"
)
func?minRefuelStops(target?int,?startFuel?int,?stations?[][]int)?int?{
????if?startFuel?>=?target?{
????????return?0
????}
????//?大根堆
????//?維持的是：最值得加油的加油站，有多少油
????//?最值得：加得次數(shù)少，跑的還最遠
????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實現(xiàn)大根堆
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
}
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;
????}
????//?大根堆
????//?維持的是：最值得加油的加油站，有多少油
????//?最值得：加得次數(shù)少，跑的還最遠
????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實現(xiàn)大根堆，這里用函數(shù)指針代替仿函數(shù)
int?cmp(int?a,?int?b)?{
????return?a?<?b;
}
//?交換兩個數(shù)的值
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;
????}
????//?大根堆
????//?維持的是：最值得加油的加油站，有多少油
????//?最值得：加得次數(shù)少，跑的還最遠
????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實現(xiàn)大根堆
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;
????}
????//?大根堆
????//?維持的是：最值得加油的加油站，有多少油
????//?最值得：加得次數(shù)少，跑的還最遠
????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.top();
????????????????heap.pop();
????????????????cnt++;
????????????????if?(to?>=?target)?{
????????????????????return?cnt;
????????????????}
????????????}
????????????if?(to?<?position)?{
????????????????return?-1;
????????????}
????????}
????????heap.push(fuel);
????}
????//?最后一個加油站的位置，都達到了
????//?但還沒有到target
????while?(!heap.empty())?{
????????to?+=?heap.top();
????????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;
}
福大大架構師每日一題
java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡，操作系統(tǒng)。
公眾號
