Gas station 的另一种解题思路# JobHunting - 待字闺中
s*r
1 楼
今天做了 Gas station，然后来看讨论发现市面上的解法已经很经典，通过计算所有和
检测是否有解，通过计算部分和找到 index。
本题本质是找到一个序列使所有前缀和非负。所以是这样想的，假设 index 0 （用
beg 表示）就是解，如果假设成立，那么从这开始的前缀和（假设已经走到了 end）都
是非负的，一直累加。然而一旦发现不成立，那么就退一步把 beg 设为 beg - 1 作为
候选。直到 beg == end。这样只要一个累加和就好了。
初始时把 beg = 0, end = (beg + 1) % n ，更新时是 beg = (beg - 1 + n) % n，
end = (end + 1) % n，但这样并不美观。所以技巧是把 beg 初值设为 n - 1，end 设
为 0，两数更新就都是单调的了。
class Solution {
public:
int canCompleteCircuit(vector &gas, vector &cost) {
int beg = gas.size() - 1, end = 0;
int sum = gas[beg] - cost[beg];
while (beg != end) {
if (sum < 0) {
--beg;
sum += gas[beg] - cost[beg];
} else {
sum += gas[end] - cost[end];
++end;
}
}
return (sum >= 0) ? (beg) : (-1);
}
};
当然可以写一个省字节的脑残解，just more fun
class Solution {
public:
int canCompleteCircuit(vector &gas, vector &cost) {
int beg = gas.size() - 1, end = 0;
int sum = gas[beg] - cost[beg];
while (beg != end) {
int k = (sum < 0) ? (--beg) : (end++);
sum += gas[k] - cost[k];
}
return (sum >= 0) ? (beg) : (-1);
}
};
检测是否有解，通过计算部分和找到 index。
本题本质是找到一个序列使所有前缀和非负。所以是这样想的，假设 index 0 （用
beg 表示）就是解，如果假设成立，那么从这开始的前缀和（假设已经走到了 end）都
是非负的，一直累加。然而一旦发现不成立，那么就退一步把 beg 设为 beg - 1 作为
候选。直到 beg == end。这样只要一个累加和就好了。
初始时把 beg = 0, end = (beg + 1) % n ，更新时是 beg = (beg - 1 + n) % n，
end = (end + 1) % n，但这样并不美观。所以技巧是把 beg 初值设为 n - 1，end 设
为 0，两数更新就都是单调的了。
class Solution {
public:
int canCompleteCircuit(vector
int beg = gas.size() - 1, end = 0;
int sum = gas[beg] - cost[beg];
while (beg != end) {
if (sum < 0) {
--beg;
sum += gas[beg] - cost[beg];
} else {
sum += gas[end] - cost[end];
++end;
}
}
return (sum >= 0) ? (beg) : (-1);
}
};
当然可以写一个省字节的脑残解，just more fun
class Solution {
public:
int canCompleteCircuit(vector
int beg = gas.size() - 1, end = 0;
int sum = gas[beg] - cost[beg];
while (beg != end) {
int k = (sum < 0) ? (--beg) : (end++);
sum += gas[k] - cost[k];
}
return (sum >= 0) ? (beg) : (-1);
}
};
