fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
当老司机学会了贪心算法 :: labuladong的算法小抄
@naruuu-xx 感谢指出，已修复，这里是我考虑不周，只要把 minSum = Integer.MAX_VALUE 改为 minSum = 0 就行了
贪心解法后一个返回值可以直接返回 return start;。
因为start的初始值为0，若初始值为0不满足，后面也不会出现 start == n 的情况。
不好意思,我有点晕, 这图像法的图是用的哪个case? 比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2] 那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]
不好意思,我有点晕, 这图像法的图是用的哪个case? 比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2] 那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]
- 建议仔细看看那个图，是将图整体沿
y轴整体上移，将最低的作为起点，并不是说一定要从0出发 - sum其实一直随着start位置不同，而在更新，不一定全是以0为参照的，起点换了，sum不久换了吗，对吧。
- 仔细看看题目，题目中说返回出发时的加油站编号。题目的意思是，让你求一个出发的加油站编号，使得能顺利绕一周。
不好意思,我有点晕, 这图像法的图是用的哪个case? 比如第一个用例: gas:[1,2,3,4,5]; cost:[3,4,5,1,2] 那么 sum难道不应该是 sum: [0, -2, -4, -6, -3, 0]
- 建议仔细看看那个图，是将图整体沿
y轴整体上移，将最低的作为起点，并不是说一定要从0出发- sum其实一直随着start位置不同，而在更新，不一定全是以0为参照的，起点换了，sum不久换了吗，对吧。
- 仔细看看题目，题目中说返回出发时的加油站编号。题目的意思是，让你求一个出发的加油站编号，使得能顺利绕一周。
我说的是这个图, labuladong描述的很清楚."我们不妨就把0作为起点...."
2. 起点没有换.就算是换也是下一张图的事情.
3. 我理解题目,但是你没有理解我的问题.
如果例子就是题目中的例子: gas = [1,2,3,4,5] cost=[3,4,5,1,2] 如果按照文中累加和的代码:
int n = gas.length, sum = 0;
for (int i = 0; i < n; i++) {
// 计算累加和
sum += gas[i] - cost[i];
}
那么: sum :0 i=0: sum = 1-3 = -2 i=1: sum = -2 + 2 - 4 = 0 i=2: sum = 0 + 3-5 = -2 i=3: sum = -2 + 4-1 = 1 i=4: sum = 1 +5 - 2 = 4
怎么算也不会有上面的那个曲线.
如果例子就是题目中的例子: gas = [1,2,3,4,5] cost=[3,4,5,1,2] 如果按照文中累加和的代码:
int n = gas.length, sum = 0; for (int i = 0; i < n; i++) { // 计算累加和 sum += gas[i] - cost[i]; }那么: sum :0 i=0: sum = 1-3 = -2 i=1: sum = -2 + 2 - 4 = 0 i=2: sum = 0 + 3-5 = -2 i=3: sum = -2 + 4-1 = 1 i=4: sum = 1 +5 - 2 = 4
怎么算也不会有上面的那个曲线.
个人认为 只是举个例子嘛 ， 能让人看懂就行，没必要和题目给出的示例一样。只要意思能表达出来就行 😄
@tommy-qichang 我随便编的 case，不是题目给的，理解意思就好
谢谢解释. 能够理解什么意思,但是如果图文匹配就更好了 :-) 👍
dong哥好，贪心解法的注释 // 无法从 start 走到 i 我理解应该是 // 无法从 start 走到 i+1个加油站 ? 因为判断if tank<0之前已经加上i到i+1这段路径的加油量gas[i]和损失量-cost[i]了
