杭州 手机网站建设,做淘客网站怎么样,3d建模师的就业前景,漳浦县网站建设题目描述 一.原本暴力算法
最初的想法是#xff1a;先比较gas数组和cost数组的大小#xff0c;找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点#xff0c;就不能作为起始点)。当找到过后#xff0c;再去依次顺序跑一圈#xff0c;如果剩余的油为负数…题目描述 一.原本暴力算法
最初的想法是先比较gas数组和cost数组的大小找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点就不能作为起始点)。当找到过后再去依次顺序跑一圈如果剩余的油为负数再去寻找下一个满足条件的起始站点。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int index -1; //定义初始起点int left 0; //定义剩余油量bool flag false;int n gas.size();//寻找起始位置for(int i 0;in;i){if(gas[i] cost[i]) {continue;}else{index i; int j index;int count 0;coutindexindexendl;while(true){j j%n;coutjjendl;if(left 0) {left 0;break;}if(count n){flag true;return index;}left left gas[j] - cost[j];coutleftleftendl;count;j;} }}//判断if(flag){return index;}else{return -1;}}
}; 但是代码最后超时了
时间复杂度是O(N^2) 因为循环遍历寻找起始站点找到过后再去循环遍历走一圈是O(N^2的时间复杂度
巧妙思路算法二能通过的
转子大佬的代码。 情况一如果gas的总和小于cost总和那么无论从哪里出发一定是跑不了一圈的 情况二rest[i] gas[i]-cost[i]为一天剩下的油i从0开始计算累加到最后一站如果累加没有出现负数说明从0出发油就没有断过那么0就是起点。 情况三如果累加的最小值是负数汽车就要从非0节点出发从后向前看哪个节点能把这个负数填平能把这个负数填平的节点就是出发节点。 class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int min INT_MAX; // 从起点出发油箱里的油量最小值for (int i 0; i gas.size(); i) {int rest gas[i] - cost[i];curSum rest;if (curSum min) {min curSum;}}if (curSum 0) return -1; // 情况1if (min 0) return 0; // 情况2// 情况3for (int i gas.size() - 1; i 0; i--) {int rest gas[i] - cost[i];min rest;if (min 0) {return i;}}return -1;}
}; 在这里时间复杂度O(N) 空间复杂度O(1)没有开辟新的空间
二.贪心算法
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
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) { // 当前累加rest[i]和 curSum一旦小于0start i 1; // 起始位置更新为i1curSum 0; // curSum从0开始}}if (totalSum 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};
时间复杂度O(N)
转载于代码随想录大佬的算法
