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 的大作中提到】 : 太牛逼了,第二段几乎就是数学证明。所以这个题如果是不是唯一解的话好像还没法做?
|