一.题目介绍
1.题目来源
链接：LeetCode
2.题目
在一条环路上有n个加油站，其中第i个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组gas和cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。
二.具体实现
1.实现思路
考虑暴力破解，一方面是验证下自己对题目的理解是否正确，另一方面后续的优化也可以从这里入手。 考虑从第 0 个点出发，能否回到第 0 个点。 考虑从第 1 个点出发，能否回到第 1 个点。 考虑从第 2 个点出发，能否回到第 2 个点。 ...... 考虑从第 n 个点出发，能否回到第 n 个点。 由于是个圆，得到下一个点的时候我们需要取余数。 另外针对暴力法，优化算法主要从圆上入手 复制代码
2.实现代码
1)暴力法，缺点很明显，每一步都需要避开圆
public int canCompleteCircuit(int[] gas, int[] cost) { //汽油 int n = gas.length; //考虑从每个点出发 for (int i = 0; i < n; i++) { int j = i; int remain = gas[i]; //说明可以到达下一个点 while (remain -cost[j] >=0){ //减去花费的 + 新的补给的 remain = remain - cost[j] + gas[(j+1) % n]; j = (j + 1) % n; //j 回到了 i if (j == i) { return i; } } } return -1; } 复制代码
2)针对暴力法的优化算法
public int canCompleteCircuit1(int[] gas, int[] cost) { int n = gas.length; for (int i = 0; i < n; i++) { int j = i; int remain = gas[i]; while (remain - cost[j] >= 0) { //减去花费的加上新的点的补给 remain = remain - cost[j] + gas[(j + 1) % n]; j = (j + 1) % n; //j 回到了 i if (j == i) { return i; } } if (j < i) { return -1; } //i 直接跳到 j，外层 for 循环执行 i++，相当于从 j + 1 开始考虑 i = j; } return -1; } 复制代码
3.运行结果
三.题后思考
可以看出来，即使是优化后的算法，其实也不是最优解。有时候自己一直找不到突破口是因为自己把问题想困难了，其实有的问题很简单，需要不断的分解。无论怎么样，这也是自己思考后的产物，算法题，每做一题再去看题友的解决方案都有所收获，哦，原来这个题还能这么做，也算是每天进步一点点吧，加油！
