怎样做才能让网站更受关注,福州开发网站公司,平湖网站建设公司,网站的构成要素目录标题 134. 加油站 贪心思想#xff1a; 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件#xff1a; 最优子结构#xff1a;规模较大的问题的解由规模较小的子问题的解组成#xff0c;规模较大的问题的解只由其中一个规模较小的子问题的解决定… 目录标题 134. 加油站 贪心思想 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件 最优子结构规模较大的问题的解由规模较小的子问题的解组成规模较大的问题的解只由其中一个规模较小的子问题的解决定无后效性后面阶段的求解不会修改前面阶段已经计算好的结果贪心选择性质从局部最优解可以得到全局最优解。 综上可得贪心算法就是做出当前状态下的最优选择认为就可以解决问题。 在本题中要找到一个位置能够绕行一周回来。 “假设从x加油站出发经过z加油站最远能到达y加油站那么从z加油站直接出发不可能到达y下一个加油站。因为从x出发到z加油站时肯定 有存储的油 或者 到z的时候油已经没了加上z加油站能够加上的油这都到不了y的下一站。而直接从z出发刚开始是没有存储的油的所以更不可能到达y的下一站。” 也就是说我们首先检查第 0 个加油站并试图判断能否环绕一周如果不能就从第一个无法到达的加油站开始继续检查。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int length gas.length;int index 0;// 这里不用for循环是因为我们会使用跳过一些下标。所以使用while是最好的// 从头到尾遍历每个加油站并且检查以该加油站为起点能否行驶一周while (index length) {// 当前index加油站的总汽油int sumOfGas 0;// 当前index加油站的总花费汽油int sumOfCost 0;// 当前index加油站最远能够走的最远步数int count 0;// 判断从当前index下标出发能否环形一周while (count length) {// 当前index加油站组成环形加油站// 环形加油站下标int currentIndex (index count) % length;sumOfCost cost[currentIndex];sumOfGas gas[currentIndex];// 如果这个环形下标站点发现油不够了if (sumOfCost sumOfGas) {// 当前index加油站组成环形加油站肯定是不满足题意的跳出循环break;}// 最远的步数1count;}// 当前index能够环形一周if (count length) {// 返回return index;} else {// 就从无法到达的加油站开始继续检查。index index count 1;}}// 所有加油站作为起点都不满足return -1;}
}
