科技有限公司 网站制作,Wordpress页面怎么使用,东莞企业网站后缀,wordpress网站不安全题意理解#xff1a; 给定n个站点#xff0c;两个数组gas表达每个站点可加的油量#xff0c;cost表达到下一站点所需耗费的油量。 gas [1,2,3,4,5], cost [3,4,5,1,2] 要求从下表为i的站点开始#xff0c;刚好能支撑汽车在每个站点转一圈后回到出发位置。 解题思路#… 题意理解 给定n个站点两个数组gas表达每个站点可加的油量cost表达到下一站点所需耗费的油量。 gas [1,2,3,4,5], cost [3,4,5,1,2] 要求从下表为i的站点开始刚好能支撑汽车在每个站点转一圈后回到出发位置。 解题思路 当前站剩余油量累计-下一站耗油0行程被迫中止前几站到到该站剩余的油量不足以支撑这几站的油量耗费我们需要选择新的起始位置。 此时我们选择当前站的下一站作为起始站重新开始。 注意 我们总是重复此过程。则不会出现到此处行程截止但中间存在可完成行程的开始节点。 假设 位置2处截止,开往下一节点剩余油0但是存在位置1处开始到位置2开往下一节点后剩余油0, 那么 必然存在位置0-位置1,从位置1开往下一节点剩余油0, 因为 我们总是在开往下一节点剩余油0时更换起始节点 故 从位置0-位置2不存在一个可开始的位置1使位置1到位置2开往下一节点剩余油0。 所以 当开往下一节点剩余油0时将当前节点的下一个节点作为起始节点是合理的。 其次 若所有站点油和所有路程耗费则说明任何一个节点开始都无法完成形成返回下标-1. 1.贪心解题
public int canCompleteCircuit(int[] gas, int[] cost) {int start0;int curGos0;int totalGos0;for(int i0;i gas.length;i){//当起始位置到此处时开往下一节点剩余油0,行程截止if(curGos0){//更换起始位置重新开始计算curGos0;starti;}curGos(gas[i]-cost[i]);totalGos(gas[i]-cost[i]);//记录所有行程耗油剩余量}//若所有节点耗油剩余量0,则从任何节点开始都走不完行程。if(totalGos0) return -1;return start;}
2.分析 时间复杂度O(n) 空间复杂度O(1) n表示输入数组的大小
