在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。 请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。 题目数据可以保证最多有一个答案。 数据范围: , gas 和 cost 数组中的值满足-笔试面试资料

这是qklbishe.com第19335 篇笔试面试资料
提供答案分析,通过本文《在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。 题目数据可以保证最多有一个答案。
数据范围: , gas 和 cost 数组中的值满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。
题目数据可以保证最多有一个答案。
数据范围: 在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。          请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。    题目数据可以保证最多有一个答案。          数据范围:  , gas 和 cost 数组中的值满足 , gas 和 cost 数组中的值满足 在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。          请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。    题目数据可以保证最多有一个答案。          数据范围:  , gas 和 cost 数组中的值满足
Java

在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。          请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。    题目数据可以保证最多有一个答案。          数据范围:  , gas 和 cost 数组中的值满足 零葬

时间复杂度O(n2)的解法还是比较好想的,首先构建一个“纯能值”数组energy(用gas减去cost)。其中的元素energy[i]表示如果从i加油站开车去往下一个加油站i+1,可以给下一个加油站带去多少油。如此一来,只有在energy[i]非负的情况下,i才有可能是符合题意的出发点,这样可以过滤掉一些明显不合题意的加油站。
而根据energy数组的含义我们就能明白,其中的元素表示在车行驶到某个加油站时的剩余油量。因此随便选择一个加油站出发,如果累加一圈的过程中出现了负数,那肯定就无法从这个加油站出发环绕一周。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param gas int整型一维数组       * @param cost int整型一维数组       * @return int整型      */     public int gasStation (int[] gas, int[] cost) {         // write code here         LinkedList<Integer> candicates = new LinkedList<>();         int n = gas.length;         for(int i = 0; i < n; i++){             gas[i] -= cost[i];             if(gas[i] >= 0){                 candicates.add(i);             }         }         while(!candicates.isEmpty()){             int startPoint = gameStarted(gas, candicates.removeFirst());             if(startPoint != -1){                 return startPoint;             }         }         return -1;     }          private int gameStarted(int[] energy, int start) {         int cur = start;         int cumsum = energy[cur];         cur++;         if(cur == energy.length) cur = 0;         while(cur != start){             if(cumsum >= 0){                 cumsum += energy[cur];                 cur++;                 if(cur == energy.length) cur = 0;             }else{                 return -1;     // 累加一圈出现了负数             }         }         return start;     } }

今天 15:28:33 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 在一条环路上有 n 个加油站,其中第 i 个加油站有 gas[i] 升油,假设汽车油箱容量无限,从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。 请问能否绕环路行驶一周,如果可以则返回出发的加油站编号,如果不能,则返回 -1。 题目数据可以保证最多有一个答案。 数据范围: , gas 和 cost 数组中的值满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情