苏州企业门户网站,怎么在网站上建设投票统计,可以做任务挣钱的网站,绍兴网站制作系统提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 目录
一、问题描述
二、原始解法
总结 提示#xff1a;以下是本篇文章正文内容#xff0c;下面案例可供参考
一、问题描述
在一条环路上有N个加油站#xff0c;其中第… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 目录
一、问题描述
二、原始解法
总结 提示以下是本篇文章正文内容下面案例可供参考
一、问题描述
在一条环路上有N个加油站其中第i个加油站有汽油 a[i] 升
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 b[i] 升。你从其中的一个加油站出发开始时油箱为空。
如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1
输入: a [1,2,3,4,5] b [3,4,5,1,2] 输出: 3
输入: a [2,3,4] b [3,4,3] 输出: -1
二、原始解法 解题思路
首先汽车是加了油然后才能跑下一段路程到下一个目的地如果油量不足就从下一个目的地始发循环往复直到最后一个目的地如果最后一个目的地符合则需要从第一个节点再重新出发到达倒数第二个节点这样就完成了整个环行路的遍历。
代码示例
public void test() {// 记录油量int[] a new int[]{2, 4, 5};// 记录每一段举例的路程int[] b new int[]{3, 5, 6};// 记录从第几个节点出发int index 0;// 记录剩余油量int left 0;boolean result true;while (index a.length) {for (int i index; i a.length; i) {if (left a[i] b[i]) {// 当前节点出发不能满足, 则记录节点的索引index向前推进, index直接跳到下一个节点, 即为i1index i 1;// 重置剩余油量left 0;// 设置当前结果result false;continue;}// 计算剩余油量left left a[i] - b[i];// 设置当前结果result true;}// 从0开始, 整个循环如果结束, 且结果为通过, 则跳出while循环if (result) {break;}}// 如果index位于0到a.length-1之间, 说明前边是成功的, 需要将0到index之间的再走一遍, 这一遍比较特殊, 只需要从前到后判断一次即可if (index 0 index a.length left 0) {for (int i 0; i index; i) {if (left a[i] b[i]) {// 不通过, 设置最后的结果result false;// 跳出循环break;}// 计算剩余油量left left a[i] - b[i];// 设置当前结果result true;}}// 输出结果System.out.println(result);// 输出第一个符合的出发点System.out.println(index a.length ? index : -1);}
这种算法理解起来比较简单主要要记录一下本次出发的起点结果以及剩余油量
当遇到类似的问题时可以先用最小的例子来攻破比如我们就用两个数组每个数组里只有2个元素推导一下整个过程然后转化成代码然后再验证随后再增加到3个元素进行验证查漏补缺基本上就没问题了。
三、原始解法-简化
解题思路
在上边思路的基础上从另一个角度去想首先我们要保证油的总量要大于等于路程其次找到出发的位置这个位置出发加上后续的补充能保证油是足够的。
代码示例
public void test1() {int[] a new int[]{1, 3, 8};int[] b new int[]{2, 4, 5};int index 0, total 0, left 0;for (int i 0; i a.length; i)if ((left left a[i] - b[i]) 0) {index i 1;total left;left 0;}System.out.println((total left 0) ? -1 : index);
}
这种解法省略了从中部节点开始到绕回来从0开始的这段逻辑。增加了一个油-路程差值的统计。 总结
复杂的搞不懂先上简单的算法简单到有手就行
