网站开发 毕业答辩ppt,湖南seo优化哪家好,网站后台无上传图片按钮,清新太和做网站写在前面 据说#xff0c;这是一道被华为 2021、2022 和 2023 都出过的题目 #x1f923; 华为是「卷」的发明者#xff0c;但不是「内卷」发明者#xff0c;毕竟只有华为是实打实的给加班费。 这么卷的公司#xff0c;怎么也不更新一下题库。 难道没人做出来就不用考虑换… 写在前面 据说这是一道被华为 2021、2022 和 2023 都出过的题目 华为是「卷」的发明者但不是「内卷」发明者毕竟只有华为是实打实的给加班费。 这么卷的公司怎么也不更新一下题库。 难道没人做出来就不用考虑换题再这么搞可就成为背诵材料了 流水的候选人铁打的题 题目描述 平台LeetCode 题号871 汽车从起点出发驶向目的地该目的地位于出发位置东面 target 英里处。 沿途有加油站每个 station[i] 代表一个加油站它位于出发位置东面 station[i][0] 英里处并且有 station[i][1] 升汽油。 假设汽车油箱的容量是无限的其中最初有 startFuel 升燃料。它每行驶 英里就会用掉 升汽油。 当汽车到达加油站时它可能停下来加油将所有汽油从加油站转移到汽车中。 为了到达目的地汽车所必要的最低加油次数是多少如果无法到达目的地则返回 。 注意如果汽车到达加油站时剩余燃料为 它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 仍然认为它已经到达目的地。 示例 1 输入target 1, startFuel 1, stations []输出0解释我们可以在不加油的情况下到达目的地。 示例 2 输入target 100, startFuel 1, stations [[10,100]]输出-1解释我们无法抵达目的地甚至无法到达第一个加油站。 示例 3 输入target 100, startFuel 10, stations [[10,60],[20,30],[30,30],[60,40]]输出2解释我们出发时有 10 升燃料。我们开车来到距起点 10 英里处的加油站消耗 10 升燃料。将汽油从 0 升加到 60 升。然后我们从 10 英里处的加油站开到 60 英里处的加油站消耗 50 升燃料并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。我们沿途在1两个加油站停靠所以返回 2 。 提示 贪心 优先队列堆 我们可以模拟行进过程使用 n 代表加油站总个数idx 代表经过的加油站下标使用 remain 代表当前有多少油起始有 remain startFuel)loc 代表走了多远ans 代表答案至少需要的加油次数。 只要 loc target代表还没到达经过目标位置我们可以继续模拟行进过程。 每次将 remain 累加到 loc 中含义为使用完剩余的油量可以去到的最远距离同时将所在位置 stations[idx][0] loc 的加油站数量加入优先队列大根堆根据油量排倒序中。 再次检查是否满足 loc target下次循环此时由于清空了剩余油量 remain我们尝试从优先队列大根堆中取出过往油量最大的加油站并进行加油同时对加油次数 ans 进行加一操作。 使用新的剩余油量 remain 重复上述过程直到满足 loc target 或无油可加。 容易证明该做法的正确性同样是消耗一次加油次数始终选择油量最大的加油站进行加油可以确保不存在更优的结果。 Java 代码 class Solution { public int minRefuelStops(int target, int startFuel, int[][] stations) { PriorityQueueInteger q new PriorityQueue((a,b)-b-a); int n stations.length, idx 0; int remain startFuel, loc 0, ans 0; while (loc target) { if (remain 0) { if (!q.isEmpty() ans 0) remain q.poll(); else return -1; } loc remain; remain 0; while (idx n stations[idx][0] loc) q.add(stations[idx][1]); } return ans; }} C 代码 class Solution {public: int minRefuelStops(int target, int startFuel, vectorvectorint stations) { priority_queueint q; int n stations.size(), idx 0; int remain startFuel, loc 0, ans 0; while (loc target) { if (remain 0) { if (!q.empty() ans 0) { remain q.top(); q.pop(); } else { return -1; } } loc remain; remain 0; while (idx n stations[idx][0] loc) q.push(stations[idx][1]); } return ans; }}; Python 代码 class Solution: def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) - int: q [] n, idx len(stations), 0 remain, loc, ans startFuel, 0, 0 while loc target: if remain 0: if q: ans 1 remain -heappop(q) else: return -1 loc, remain loc remain, 0 while idx n and stations[idx][0] loc: heappush(q, -stations[idx][1]) idx 1 return ans 时间复杂度 空间复杂度 总结 贪心 优先队列堆其实是一类问题。 出现频率仅次于「贪心 排序」的搭配。 两种做法本质都是在决策过程中按优先取最值的方式进行贪心。 后面会起一个专门的「贪心」专题来讲此类题欢迎关注。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
