网站建设自助建站云建站,营销型网站建设就找山东艾乎建站,东莞个人网站建设,关键词优化seo排名在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;开始时油箱为空。
给定两个整数数组 gas 和 cost 其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。
思路一贪心
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){int profile[gasSize];int start 0,sum 0;for(int i 0;igasSize;i){profile[i] gas[i] - cost[i];if(profile[i]profile[start])start i;sumprofile[i];}if(sum0)return -1;return start;}
分析
本题分析题意即找到一条路径使总和大于耗油量即可利用for循环列举每个站点到结尾的情况当profile[i]profile[start]即初始油量最大时可从此开始不满足到达终点的情况则返回-1
总结
本题考察贪心的应用不断向后判断是否补给油量大于当前油量最后判断总和是否大于耗油量返回开始的位置
