| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章目录
1. 贪心
| 解题思路：时间复杂度O( n n n)，空间复杂度O( 1 1 1) |
|---|
- 暴力解法，从头到尾遍历加油站，以当前加油站为起点，判断是否可以行驶一周，时间复杂度为 O ( n 2 ) O(n^2) O(n2)
- 贪心思想，减小被检查加油站的数量，降低时间复杂度,只需遍历一遍数组
- 只要所有加油站的油量加起来 > 总耗油量，那就一定有一个加油站满足条件
- 但是，单纯的统计油量和花费汽油量，只能知道是否有个加油站满足条件，不能知道这个加油站是哪个
- 因此，我们需要在统计油量和花费汽油量的过程中，顺便找这个满足条件的加油站
贪心思路
- 从x出发，每经过一个加油站就加一次油（起始加油站也算），最多走到回到x为止，不多走
- 最后肯定会到达一个加油站，这个加油站有两种可能
- 回到了x，那么x就是满足条件的加油站
- 到达一个加油站Y，就走不下去了，无法回到x。
- 如果是第二种可能，到了Y，就走不下去了，
无法完成绕一圈的操作。那么一个事实是：从x和y之间的任何一个加油站出发，都无法到达y的下一个加油站- 那么很明显，贪心的思想就是，如果到y走不下去了，下次就从y+1走，同时我们需要重新统计油量和耗油量
代码思路
- 从0号加油站出发，每经过一个加油站（包括0号加油站）就统计可获得的油量总和sumOfGas，以及需要花费的油量总和sumOfCost
- 情况一：当走到y加油站时走不下去了（sumOfGas < sumOfCost），从y+1继续，同时sumOfGas 和sumOfCost归0，重新统计
- 情况二：正好绕了一圈，那么我们找到了这个加油站了
- 因为下标涉及循环，需要类似循环链表的循环下标法：下标 % 加油站数量 = 循环后的实际加油站位置。例如5个加油站，目前下标为9，那么我们在10%9 = 4号加油站，也就是最后一个加油站（下标从0开始）;
时间复杂度，最多为2*n
- 最坏情况是，情况一，从0号加油站走到y后，走不下去了，此时从y+1继续走，依然走不下去。直到所有加油站都访问过时
- 此时发现所有加油站都走过了，则没有答案。因为无法完成绕一圈的操作时，从x和y之间的任何一个加油站出发，都无法到达y的下一个加油站。另外sumOfGas < sumOfCost也证明没有答案
| 代码 |
|---|
class Solution {
//只要所有加油站的油量加起来 > 总耗油量，那就一定有一个加油站满足条件
//所以，单纯的统计油量和花费汽油量，只能知道是否有这个加油站满足条件，不能知道这个加油站是哪个
//因此，我们需要在统计油量和花费汽油量的过程中，顺便找这个满足条件的加油站
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int i = 0;//汽油下标
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;//保存有多少汽油，和需要花费多少汽油。
int cnt = 0;//当前车子走到哪里，注意这个是循环下标
//此循环中，统计油量和花费汽油量
while (cnt < n) {//cnt需要走一个循环
int j = (i + cnt) % n;//获取循环下标（因为我们可以从最后一个加油站，直接回到第一个加油站）
sumOfGas += gas[j];//每走到一个加油站，油量++，每个加油站只会累加一次
sumOfCost += cost[j];//每离开一个加油站，油量花费++。每个花费只会累加一次
if (sumOfCost > sumOfGas) {//如果花费，大于当前持有的油
break;//跳出，当前i号加油站不满足条件
}
cnt++;//否则继续行驶
}
if (cnt == n) {//如果cnt == n说明正好绕了一圈
return i;//那么i是一个合适的起点
} else {//否则内部循环遍历过的不用再次遍历
//走到这里说明已经到达的加油站，都不满足条件，直接从下一个加油站继续
i = i + cnt + 1;//从cnt当前所在加油站的下一个加油站继续走
}
//如果此时i>=n了，说明所有加油站都不合格，返回-1，否则继续循环
}
return -1;//如果最终无法到达，返回-1;
}
}
2. 动态规划
| 解题思路：时间复杂度O( n n n)，空间复杂度O( 1 1 1) |
|---|
- dp[i]=dp[i-1]+gas[i]-cost[i]，求最小的dp[i]，并且最后dp[n-1]必须>0，不然无解
- gas = [1,2,3,4,5], cost = [3,4,5,1,2]为例：dp数组为 [-2,-4,-6,-3,0]。下标i代表从0号到i号加油站。保存的值是总油量（总获取油量 - 总消耗量）
- 如果最后一个元素为>=0,那么说明有解。但是哪个是起点加油站呢，只要找到
dp数组中的最低点（最小值）的后一个即可- 因为最低点，代表左边是下降曲线（消耗量>油量），右边一定是油量大于消耗量。所以最低点的右边，是第一个油量大于消耗量的，一定是起点。但是前提是dp数组最后一个元素>=0
按照上面的想法写代码，空间复杂度为O(n), 但是我们发现，我们每次计算i号加油站的dp值，只需要前一个i-1的状态，所以全部用一个变量即可操作。从而将空间复杂度降到O(1)
| 代码 |
|---|
class Solution {
//动态规划 O(N)
//dp[i] = dp[i-1] + gas[i] - cost[i]，求最小的 dp[i]，并且最后 dp[n-1] 必须 > 0，不然无解
//gas = [1,2,3,4,5], cost = [3,4,5,1,2]
//dp数组为 [-2,-4,-6,-3,0]。下标i代表从0号到i号加油站。保存的值是总油量（总获取油量 - 总消耗量）
//如果最后一个元素为 >= 0,那么说明有解
//但是哪个是起点加油站呢，只要找到dp数组中的最低点（最小值）的后一个即可
//因为最低点，代表左边是下降曲线（消耗量>油量），右边一定是油量大于消耗量。所以最低点的右边，是第一个油量大于消耗量的，一定是起点
int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 相当于图像中的坐标点和最低点
int sum = 0, minSum = 0;//sum即表示dp[i-1]又表示dp[i],minSum保存最低点的值
int start = 0;//start保存最低点的下标
for (int i = 0; i < n; i++) {
sum += gas[i] - cost[i];//到这里，sum本身是dp[i-1],然后+=gas[i] - cost[i]，变成dp[i]本身
if (sum < minSum) {//如果sum是新的最低点
// 经过第 i 个站点后，使 sum 到达新低
// 所以站点 i + 1 就是最低点（起点）
start = i + 1;
minSum = sum;
}
}
if (sum < 0) {//dp[n-1],也就是dp数组最后一个元素，小于0的话，就无解
// 总油量小于总的消耗，无解
return -1;
}
// 环形数组特性
//如果sum，也就是dp[n - 1]>=0,说明有解，start就是起点，但是因为我们是循环数组，如果start是n,表示起点是0
return start == n ? 0 : start;
}
}