做响应式网站用什么框架,某网站seo策划方案,wordpress getterm,.net 响应式网站题目
134. 加油站
中等
相关标签
贪心 数组
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;…题目
134. 加油站
中等
相关标签
贪心 数组
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 示例 1: 输入: gas [1,2,3,4,5], cost [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油
开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油
开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油
开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油
开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油
开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。
因此3 可为起始索引。 示例 2: 输入: gas [2,3,4], cost [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油
开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油
开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油
你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。
因此无论怎样你都不可能绕环路行驶一周。 提示:
gas.length ncost.length n1 n 1050 gas[i], cost[i] 104 思路和解题方法 一暴力 目标是判断给定的汽油站能否构成一个环路使得可以从某个站点出发顺时针往前绕一圈返回该站点。每个站点有两个属性gas[i] 表示在该站点加油可获得的油量cost[i] 表示从该站点到下一个站点需要消耗的油量。为了判断是否可以行驶一圈我们可以模拟一遍整个过程。假设从第 i 个站点出发开始时剩余油量为 gas[i]−cost[i]依次到达第 i1,i2,...,n−1,0,1,...,i−1 个站点每经过一个站点就用消耗的油量减去加入的油量同时记录当前的剩余油量。如果最后回到了起点且剩余油量不小于 0则说明可以完成一次环形行驶。 复杂度 时间复杂度: O(n*n) 时间复杂度: O(n*n)n 是站点数因为每个站点都可能做一次循环检查。 空间复杂度 O(1) 空间复杂度: O(1)只需要常数个变量记录当前状态即可。 c 代码 一 暴力
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {for (int i 0; i cost.size(); i) { // 对于每一个点以它为起点做一次循环检查int rest gas[i] - cost[i]; // 记录当前点的剩余油量int index (i 1) % cost.size(); // 初始化index指向下一个点while (rest 0 index ! i) { // 如果还有油且没有回到起点就继续往前走rest gas[index] - cost[index]; // 更新剩余油量index (index 1) % cost.size();// 更新下一个点}if (rest 0 index i) { // 如果油足够到达终点并回到起点了就返回起点return i;}}return -1; // 否则返回-1}
};思路和解题方法 二贪心 当我们遍历每个站点时我们首先更新curSum和totalSum。curSum是从起始位置到当前位置的累加剩余油量它等于上一个位置的curSum加上当前站点的剩余油量(gas[i] - cost[i])。totalSum是所有站点的累加剩余油量它等于上一个位置的totalSum加上当前站点的剩余油量(gas[i] - cost[i])。 接下来我们判断curSum是否小于0如果小于0说明从起始位置到达当前位置的路径不可行。因为如果从起始位置开始累加剩余油量一直小于0那么无论从哪个位置出发都无法完成一次环形行驶。所以我们将起始位置更新为当前位置的下一个位置(i 1)并且重置curSum为0相当于重新开始计算累加剩余油量。 最后我们在遍历结束后检查totalSum是否小于0。如果totalSum小于0说明所有站点的累加剩余油量都是负数即无法完成一次环形行驶返回-1。否则我们返回起始位置start因为凡是能够完成一次环形行驶的情况下start位置一定是符合条件的。 复杂度 时间复杂度: O(n) 时间复杂度: O(n)其中n是站点数。遍历一次所有站点进行累计操作。 空间复杂度 O(1) 空间复杂度: O(1)只需要常数个变量记录当前状态。 c 代码 二 贪心
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) {curSum gas[i] - cost[i]; // 更新当前累加剩余油量totalSum gas[i] - cost[i]; // 更新总累加剩余油量if (curSum 0) { // 当前累加剩余油量小于0说明从起始位置到达当前位置的路径不可行start i 1; // 更新起始位置为当前位置的下一个位置curSum 0; // 重置当前累加剩余油量为0}}if (totalSum 0) return -1; // 总累加剩余油量小于0说明无法完成一次环形行驶返回-1return start; // 返回起始位置}
};对于这里的解释 curSum gas[i] - cost[i]; // 更新当前累加剩余油量totalSum gas[i] - cost[i]; // 更新总累加剩余油量if (curSum 0) { // 当前累加剩余油量小于0说明从起始位置到达当前位置的路径不可行start i 1; // 更新起始位置为当前位置的下一个位置curSum 0; // 重置当前累加剩余油量为0} 更新当前累加剩余油量(curSum): curSum从上一个站点累加的剩余油量加上当前站点的剩余油量(gas[i] - cost[i])得到。 更新总累加剩余油量(totalSum): totalSum从上一个站点累加的剩余油量加上当前站点的剩余油量(gas[i] - cost[i])得到。 curSum的作用是判断从起始位置到达当前位置的路径是否可行。如果curSum小于0说明从起始位置到达当前位置的路径不可行因为从起始位置开始到当前位置油量一直不足不可能顺利到达当前位置更别说从当前位置继续走了。所以我们需要将起始位置更新为当前位置的下一个位置(i1)并将curSum重置为0相当于重新开始计算从新的起始位置到哪个位置的路径可行。 totalSum的作用是判断整个环路是否可行。如果totalSum小于0说明所有站点的总剩余油量是负数即无法完成一次环形行驶返回-1即可。 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
