好看的企业网站源码,互联网网站排名,中国交通建设集团官网,重庆ssc做号网站目录 一#xff0c;题目
二#xff0c;题目接口 三#xff0c;解题思路及其代码 一#xff0c;题目 在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油…
目录 一题目
二题目接口 三解题思路及其代码 一题目 在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。 给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 二题目接口
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {}
}; 三解题思路及其代码 1.暴力解法 其实对于这道题很容易想到的便是一个暴力解法这个暴力解法的大概思路便是对每一个下标下进行试验如果我的这个下标在经过一圈之后能回到我原来的下标的话那么我这个下标便是能够符合条件的。 如何找到符合条件的下标呢 1.若该下标的restgas[i]-cost[i]是整数那我便可以到达下一个加油站。 2.为了防止我的下标越界必须有%n的操作n是数组的长度。 代码 class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int n gas.size();//计算长度int startPos 0;//从零开始出发for(int i 0;in;i)//遍历找正确的加油站{startPos i;int rest 0;//记录车箱里剩余的油while(gas[startPos%n]restcost[startPos%n]startPos2*n)//若符合条件便可到达下一个加油站{rest gas[startPos%n] - cost[startPos%n]rest;//记录剩余的油startPos;int pos startPos%n;if(pos i)//判断是否回到出发时的加油站处{return i;//回到了便可以返回这个加油站的下标}}}return -1;//没有这样的加油站便返回-1}
}; 对于暴力解法肯定是会超时的 所以我们就得开始写一个贪心的解法。 2.贪心解法 如何实现贪心呢先来举个例子 比如我的gas [5,1,2,3,4],cost [4,4,1,5,1] 我们可以先来计算一下这两个数组之间的差用一个diff数组记录下来diff [1,-3,1,-2,3] 首先我们先以第一个1位起点 因为我们的1是一个正数所以我可以往后走。但是在遇到-3时我的1-3为负数所以我就不能再往下走了这时贪心的地方便来了我就得从-3的下一位开始走了。 仿照这个思路改造一份贪心代码并注意越界问题代码如下 class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int n gas.size();int rest 0;for(int i 0;in;i){int rest 0;int step 0;for( ;stepn;step){rest restgas[(istep)%n]-cost[(istep)%n];if(rest0){break;}}if(rest0){return i;}istep;//加step步再加上for里面的便是增加step1步}return -1;}
}; 过啦
