s*****r
发帖数: 108 | 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);
}
}; |
s********u
发帖数: 1109 | 2 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
我写的：
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
} |
s*****r
发帖数: 108 | 3 你这个就是市面上的经典解法，我非常喜欢这个思路。我那个不像 DP 的思考方式，随
便丢一个说它是解，累加违规就看看它前面一个是不是解，其实确实继续用了前面当子
结构
【在 s********u 的大作中提到】
: 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
: 我写的：
: for(int i = 0; i < size; i++){
:
: sum += gas[i] - cost[i];
:
: if(subSum > 0)
: subSum += gas[i] - cost[i];
: else{
: subSum = gas[i] - cost[i];
|
s*****r
发帖数: 108 | 4 今天做了 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);
}
}; |
s********u
发帖数: 1109 | 5 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
我写的：
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
} |
s*****r
发帖数: 108 | 6 你这个就是市面上的经典解法，我非常喜欢这个思路。我那个不像 DP 的思考方式，随
便丢一个说它是解，累加违规就看看它前面一个是不是解，其实确实继续用了前面当子
结构
【在 s********u 的大作中提到】
: 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
: 我写的：
: for(int i = 0; i < size; i++){
:
: sum += gas[i] - cost[i];
:
: if(subSum > 0)
: subSum += gas[i] - cost[i];
: else{
: subSum = gas[i] - cost[i];
|
n*****f
发帖数: 17 | 7 其实这题你画个函数图像出来就一目了然了。f[i] = sigma{gas[j] - cost[j], j < i}
如果f[n-1] < 0，显然无论你从哪儿出发，绕一圈都会变负。如果f[n-1] >= 0，那你
总可以找到f[i]里最小的从那儿出发，无论你绕多少圈都不会变负了。 |
C****y
发帖数: 77 | 8 感觉又不像通常的DP,学习了
【在 s********u 的大作中提到】
: 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
: 我写的：
: for(int i = 0; i < size; i++){
:
: sum += gas[i] - cost[i];
:
: if(subSum > 0)
: subSum += gas[i] - cost[i];
: else{
: subSum = gas[i] - cost[i];
|
