成立网站开发公司,珠海医疗网站建设公司,私家小庭院设计实景图,网站后台添加新闻题目 测试链接 在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;开始时油箱为空。
给定两个整数数组…题目 测试链接 在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。
解释一下这道题如下图所示 路程数组gas和油耗数组cost假设从A点出发走到B点路程为1消耗油量为21 - 2 -1油量不够支撑走到B点所以如果从A点出发无法完整的绕完一圈B、C、D同理这道题就是看从哪个出发点出发后可以顺利的绕完一圈gas和cost等长。
滑动窗口 首先先将给定的 gas[] 和 cost[] 稍稍加工一下一次遍历用gas[i] - cost[i]得到的新数组中包含正负数就是从每个点出发的路程和油耗的差值看是否有能力到达下一个目的地。
此时如果用暴力方法解这道题的话只需要从0 ~ N - 1每个位置循环遍历遍历N个位置。看过程中是否出现负数如果是负数则说明不能完成循环如果不是结果 0则证明可以完成循环。
我们这里直接说用滑动窗口的解题思路 依然是先加工gas[] 和 cost[]不同的是我们要根据加工出来的gas[] - cost[]搞出来一个2倍gas[]长度的前缀和数组。
因为我们要看从 0 ~ N - 1位置中每个的出发点能否成功绕回来 gas[] - cost[] 加工出来的数组就是从每个点出发能否成功到达下一目的地的数组所以当累加到N - 1位置时下一步重新在加上 0 位置的值来构造出这个2倍长度累加和数组。
这样的做的目的是我下图中 double.length中下标4的位置可以看做是从B点出发又重新绕回A的0位置下标5的位置可以看做是从C点出发重新绕回B点的1位置。一个数组全部可以搞定。
所有原始数组中出发的位置在double.length中都可以将原始数组的累加和数组加工出来。
怎么加工 假设我从D点出发那么在gas - cost中求出来的累加和数组就是{3,2,2,4}因为要重新往A点加绕回来对应在double.length中就是划线部分怎么得出来的呢 划线数组中的每一个数都减去划线部分的前一个数1。 所以综上所述此时我们维护一个窗口最小值窗口范围就是gos.length每次窗口变化后根据窗口内最小值 - 前一个值如果此时已然 0则说明该位置不是最佳出发点。否则就认为是最佳出发点。
代码 public static int canCompleteCircuit(int[] gas, int[] cost) {boolean[] booleans goodArray(gas, cost);for (int i 0; i booleans.length; i) {if (booleans[i]) {return i;}}return -1;}public static boolean[] goodArray(int[] gas, int[] cost) {int N gas.length;int M N 1;int[] arr new int[M];for (int i 0; i N; i) {arr[i] gas[i] - cost[i];arr[N i] gas[i] - cost[i];}for (int j 1; j M; j) {arr[j] arr[j - 1];}LinkedListInteger w new LinkedList();for (int i 0; i N; i) {while (!w.isEmpty() arr[w.peekLast()] arr[i]) {w.pollLast();}w.addLast(i);}boolean[] ans new boolean[N];for (int offset 0, i 0, j N; j M; offset arr[i], j) {if (arr[w.peekFirst()] - offset 0) {ans[i] true;}if (w.peekFirst() i) {w.pollFirst();}while (!w.isEmpty() arr[w.peekLast()] arr[j]) {w.pollLast();}w.addLast(j);}return ans;}
