由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Gas station 的另一种解题思路
相关主题
请教一道面试题程序员的思维太牛逼了 (转载)
新题gas station,做出来了却没想通说几道面试题
贡献版面: Fb面经(流水账)G题一道(2)
工资涨了25%,但是扣除异地cost living差异,等于没涨,offer值得要吗?问题在哪儿啊 kth Node of BST,大家帮忙
请教 permute vector of vectors 如何实现,谢谢大家连挂
出售BrainBench 200道 C++题库rocket fuel/online test/auto racer解法
一道G的面试题。大公司女码农能干到退休吗?
Ctrl+A, Ctrl+C, Ctrl+V这道题没怎么看懂Uber电面
相关话题的讨论汇总
话题: beg话题: gas话题: end话题: sum话题: int
进入JobHunting版参与讨论
1 (共1页)
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];

1 (共1页)
进入JobHunting版参与讨论
相关主题
Uber电面请教 permute vector of vectors 如何实现,谢谢大家
请教一个经典算法问题。出售BrainBench 200道 C++题库
bloomberg面经一道G的面试题。
前缀树和后缀树一般都什么时候用啊?Ctrl+A, Ctrl+C, Ctrl+V这道题没怎么看懂
请教一道面试题程序员的思维太牛逼了 (转载)
新题gas station,做出来了却没想通说几道面试题
贡献版面: Fb面经(流水账)G题一道(2)
工资涨了25%,但是扣除异地cost living差异,等于没涨,offer值得要吗?问题在哪儿啊 kth Node of BST,大家帮忙
相关话题的讨论汇总
话题: beg话题: gas话题: end话题: sum话题: int