网站建设与管理教学视频教程,如何做网站静态页面,怎么在百度上搜到自己的网站,公司网站建设方案详细方案重启力扣每日一题系列#xff01;
因为过去两个月里掉粉掉的好严重#xff0c;我想大抵是因为更新的频率不如上半年了#xff0c;如果我重启了每日一题系列那岂不是至少是每日一更☝#x1f913;#xff1f;
也不是每天都更#xff0c;我有两不更#xff0c;特难的就不…重启力扣每日一题系列
因为过去两个月里掉粉掉的好严重我想大抵是因为更新的频率不如上半年了如果我重启了每日一题系列那岂不是至少是每日一更☝
也不是每天都更我有两不更特难的就不更了打算去算法岗的小伙伴自己琢磨去特简单的也不更了那么简单更出来岂不是拉低我的平均水准麻烦的不更太麻烦了费我时间方便的也不更直接调库就好了……
这次重启跟之前的也不一样了之前几乎每一题我都会自己作图包括动图这很花时间通常是从早上做到下午做完累了休息一下就到晚上了一天下来光力扣了。
所以这次化简了指提供思路和C示例代码咱来个力扣每日一题极速版。
废话说多了我们直接看看今天的题目。 这题其实跟昨天的题是同一个系列的但是做法上面天差地别。
先做个阅读理解简单来说就是我们一开始有一些汽油每升汽油可以走一公里某些公里处有加油站我们可以加一次油问我们最少加几次油可以走到目的地。
比较容易想到的是暴力解法我们直接模拟每到一个加油站我们都开两个分叉也就是加油或者不加油每个能到目的地的分支我们都记录下加了几次油选着最少的加油数返回即可。
不过这是困难题想都不用想也可以知道会超时没试过说不准呢
看看这可怕的数据范围。 不过知道暴力解法之后就是成功的第一步了我们要做的就是优化暴力解法这也是正常的解题过程。
因为我们要最少的加油数所以我们要尽可能的少加油但是少加油之后错过加油站了怎么办呢
现实中你会错过她但是在代码里我们不会再错过了没有对象咱就new一个嘛。
我们每经过一个加油站我们都把油搬上车等到没油了我们再加一次油因为要尽可能少加油所以每次我们都加油数最多的那一桶油这样就不会错过了。
代码中实现就是我们先行驶能跑多远跑多远然后把经过的加油站的汽油都先放到一个容器里因为我们每次要取的是最大的值所以这个容器我选择优先队列也就是大顶堆。
如果我们没跑过目的地那么我们从大顶堆里掏出一个汽油然后再接着跑反复循环直到我们跑到了目的地或者是没油了一滴都没有了。
具体可以参考下面的代码。
class Solution {
public:int minRefuelStops(int target, int startFuel, vectorvectorint stations) {priority_queueint cache; // 存放沿途的汽油int res 0; // 加油次数int cur 0, index 0; // 当前路程,stations索引(途径加油站个数)while(cur target startFuel 0){ // 不到目的地 还有汽油cur startFuel; // 前进startFuel 0; // 清零汽油while(index stations.size() stations[index][0] cur){ // 将经过的汽油记录在大顶堆中cache.push(stations[index][1]);index;}if(cur target !cache.empty()){ // 还没到目的地,那就取一次汽油,取经过的汽油中最多的 startFuel cache.top(); cache.pop();res;}}if(cur target) return res;return -1;}
};
