企业官网建设流程全解析

什么软件做网站做好,WordPress 动态内容,休闲网站建设,当下网站建设哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第八篇#xff01; 题目描述很长#xff0c;但核心很简单#xff1a; 有一些加油站围成一个圈。 gas[i]#xff1a;第 i 站有多少油。 cost[i]#xff1a;从第 i 站开到第 i1 站要耗多少油。 你有一辆油箱无限…哈喽各位我是前端小L。欢迎来到贪心算法专题第八篇题目描述很长但核心很简单有一些加油站围成一个圈。gas[i]第i站有多少油。cost[i]从第i站开到第i1站要耗多少油。你有一辆油箱无限大的车。目标找一个起点让你能绕圈跑完一周。如果找不到返回 -1。力扣 134. 加油站https://leetcode.cn/problems/gas-station/题目分析输入两个整数数组gas和cost。输出起始加油站的下标唯一解。例子gas [1, 2, 3, 4, 5]cost [3, 4, 5, 1, 2]从下标 3油4耗1出发到下标 4剩 3加 5剩 8。耗 2。到下标 0剩 6加 1剩 7。耗 3。... 一路顺风。返回 3。核心思维归零与跳跃首先有一个全局的硬性条件如果所有站点的总油量 sum(gas) 小于总消耗 sum(cost)那神仙也跑不完一圈。 直接返回 -1。接下来是贪心的核心逻辑局部最优推导。我们维护一个 curSum当前油箱余额。假设我们需要从 i 站出发。我们计算gas[i] - cost[i]这是这一站的净剩油量。我们累加这个净剩量到curSum。如果curSum 0说明车在这一站假设是j抛锚了。关键推断从i到j之间的任何一个站点k都不可能作为起点为什么因为如果你从i出发到达k时你的油箱里一定有 0的油否则你早在k之前就抛锚了。带着这些“遗产”油你都在j站死掉了如果你直接从k站白手起家初始油量为0你在j站只会死得更惨策略既然i到j都不行那我们就把起点设为j 1并把curSum归零重新开始尝试。[图解逻辑A - ... - B (死) 起点直接跳到 B1]算法流程初始化curSum 0当前连续路段的累积剩余油量。totalSum 0全局的总剩余油量用于最后判断是否有解。start 0我们假设的起点。遍历所有加油站i计算当前站的净收益rest gas[i] - cost[i]。totalSum rest。curSum rest。贪心判断如果curSum 0说明从start到i这段路走不通。更换起点start i 1。重置当前累积curSum 0。最终判断循环结束后如果totalSum 0说明总油不够返回 -1。否则返回我们最后确定的start。只要总油够且我们找到了一段路能一直走到终点那么数学上可以证明从这个start绕回前面的路也是通的。代码实现 (C)C#include vector using namespace std; class Solution { public: int canCompleteCircuit(vectorint gas, vectorint cost) { int curSum 0; int totalSum 0; int start 0; for (int i 0; i gas.size(); i) { // 计算当前站点的净剩油量 int rest gas[i] - cost[i]; totalSum rest; curSum rest; // 贪心策略如果累积油量小于0说明从 start 到 i 的区间无法连通 if (curSum 0) { // 之前的努力全部作废起点重置为下一个点 i 1 start i 1; // 油箱归零 curSum 0; } } // 全局判断如果总油量不够总消耗肯定无解 if (totalSum 0) { return -1; } // 否则最后确定的 start 就是唯一解 return start; } };深度复杂度分析时间复杂度O(N)我们只需要遍历一次数组。这比暴力法的 $O(N^2)$ 简直是质的飞跃。空间复杂度O(1)只需要几个变量。总结相信数学相信贪心这道题最难理解的地方在于为什么 totalSum 0 且 curSum 在最后一段非负就一定能保证绕圈成功这涉及到一个数学证明如果总和非负那么一定存在一个起点使得所有前缀和非负。我们通过贪心策略抛弃了所有“前缀和为负”的区间剩下的那个起点就是那个“天选之子”。贪心算法在这里表现为遇到困难负数立刻止损跳过整段困难区间寻找新的希望。下一题预告分发糖果接下来这道题是贪心算法的Hard级别题目也是面试中的“终极杀手”。一群孩子排排坐每个孩子有评分。每个孩子至少一颗糖。相邻的孩子评分高的必须获得更多的糖果。问最少需要多少糖这道题难就难在“相邻”是双向的既要比左边多又要比右边多。贪心策略教我们不要试图同时顾及两边 我们可以先从左往右遍历一次只顾左边再从右往左遍历一次只顾右边最后取最大值。准备好分糖果了吗下期见