由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 新题gas station,做出来了却没想通
相关主题
Maximum Contiguous Subarray请教一下leetcode #321. Create Maximum Number
INTERVIEW会假定你见过问的问题吗?Leetcode 689居然是fb的高频题?
programming pears上的maximum subarray算法是不是有小bug?每次刷题都有新发现
求 Maximum Subarray divide and conquer 解法[算法] unsorted array
请大牛解释一下leetcode新题新鲜的L一面
leetcode Maximum Product Subarray如果是 double 的怎么做, 假设 测试数据没有 误差请教一道面试题
关于Leetcode Maximum Subarray 的变种问题Gas station 的另一种解题思路
报个L家店面面经,求onsite bless贡献版面: Fb面经(流水账)
相关话题的讨论汇总
话题: subsum话题: index话题: sum话题: gas话题: cost
进入JobHunting版参与讨论
1 (共1页)
s********u
发帖数: 1109
1
看题目就猜到大致类似maximum subarray,用dp做:
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;
但是我自己反而是有点想不通为什么这样就可以。就是说sum >= 0,那肯定有解,但是
既然是环形的,为什么maximum subarray就是这个的解。(大致意思我们都知道,就是
说从一个比较富裕的基础出发,当然是有利的,但是因为是环形,就觉得有点诡异)有
谁能简单证明下么。。
f********4
发帖数: 988
2
如果你同意sum >= 0是有解的,而且题目说了是唯一解。那么你找到的那个index,从
这个index出发,一直到array的尾部,每一项subSum都是大于0的,这个你肯定同意,
如果不是的话,就不会返回这个index。那么接下来就到了这个index的前半部分,你怎
么证明前半部分每一项subSum 都是大于0的,因为如果每一项大于0,那index就是解。
假设前面加到某一项的时候,设为index1,subSum小于0了,那根据sum大于等于0,也
就是说从这之后的subSum加起来是大于0的(因为从index到array的尾部一直到index1相
加的subsum是小于0的,满足sum大于0,index1到index之间的subsum一定大于0)。那么
这样index1就会成为index那个返回的点,因为index1不是index,所以没有这样的点。
t******d
发帖数: 1383
3
我也做了。请帮哦留言没,看下错在哪里,一个大case没过
a********9
发帖数: 129
4
牛逼!!第一个能让我看懂的解释!!跪谢!!

【在 f********4 的大作中提到】
: 如果你同意sum >= 0是有解的,而且题目说了是唯一解。那么你找到的那个index,从
: 这个index出发,一直到array的尾部,每一项subSum都是大于0的,这个你肯定同意,
: 如果不是的话,就不会返回这个index。那么接下来就到了这个index的前半部分,你怎
: 么证明前半部分每一项subSum 都是大于0的,因为如果每一项大于0,那index就是解。
: 假设前面加到某一项的时候,设为index1,subSum小于0了,那根据sum大于等于0,也
: 就是说从这之后的subSum加起来是大于0的(因为从index到array的尾部一直到index1相
: 加的subsum是小于0的,满足sum大于0,index1到index之间的subsum一定大于0)。那么
: 这样index1就会成为index那个返回的点,因为index1不是index,所以没有这样的点。

s********u
发帖数: 1109
5
太牛逼了,第二段几乎就是数学证明。所以这个题如果是不是唯一解的话好像还没法做?

【在 f********4 的大作中提到】
: 如果你同意sum >= 0是有解的,而且题目说了是唯一解。那么你找到的那个index,从
: 这个index出发,一直到array的尾部,每一项subSum都是大于0的,这个你肯定同意,
: 如果不是的话,就不会返回这个index。那么接下来就到了这个index的前半部分,你怎
: 么证明前半部分每一项subSum 都是大于0的,因为如果每一项大于0,那index就是解。
: 假设前面加到某一项的时候,设为index1,subSum小于0了,那根据sum大于等于0,也
: 就是说从这之后的subSum加起来是大于0的(因为从index到array的尾部一直到index1相
: 加的subsum是小于0的,满足sum大于0,index1到index之间的subsum一定大于0)。那么
: 这样index1就会成为index那个返回的点,因为index1不是index,所以没有这样的点。

g**4
发帖数: 863
6
不是唯一解的话得保持2个pointer,每当sum<0,就重新开始计数,worst case也就是O(
2n)

做?

【在 s********u 的大作中提到】
: 太牛逼了,第二段几乎就是数学证明。所以这个题如果是不是唯一解的话好像还没法做?
1 (共1页)
进入JobHunting版参与讨论
相关主题
贡献版面: Fb面经(流水账)请大牛解释一下leetcode新题
Google Phone Interviewleetcode Maximum Product Subarray如果是 double 的怎么做, 假设 测试数据没有 误差
Microsoft screening programming problem关于Leetcode Maximum Subarray 的变种问题
4sum的那道题报个L家店面面经,求onsite bless
Maximum Contiguous Subarray请教一下leetcode #321. Create Maximum Number
INTERVIEW会假定你见过问的问题吗?Leetcode 689居然是fb的高频题?
programming pears上的maximum subarray算法是不是有小bug?每次刷题都有新发现
求 Maximum Subarray divide and conquer 解法[算法] unsorted array
相关话题的讨论汇总
话题: subsum话题: index话题: sum话题: gas话题: cost