两道跟circular linkedlist相关的题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

两道跟circular linkedlist相关的题。

两道跟circular linkedlist相关的题。# JobHunting - 待字闺中

i*72012-08-07 07:08

1 楼

第一题是求一个循环链表的最大和的子链表。
譬如说 1 -> -1 -> 2。然后又回到1，最大和是3，子链表是 2 -> 1。
第二题如下。
There are n gas stations positioned along a circular road. Each has a
limited supply of gas. You can only drive clockwise around the road. You
start with zero gas. Knowing how much gas you need to get from each gas
station to the next and how much gas you can get at each station, design an
algorithm to find the gas station you need to start at to get all the way
around the circle.
跪求各位大神，求思路求解答。

l*82012-08-07 07:08

2 楼

第一题，先从一个节点开始，按照最大连续和的算法计算。
回到第一个节点的时候，如果当前累积和小于等于零，算法结束。
否则，再算一轮。
O(n)算法。

an

【在 i*********7 的大作中提到】

: 第一题是求一个循环链表的最大和的子链表。
: 譬如说 1 -> -1 -> 2。然后又回到1，最大和是3，子链表是 2 -> 1。
: 第二题如下。
: There are n gas stations positioned along a circular road. Each has a
: limited supply of gas. You can only drive clockwise around the road. You
: start with zero gas. Knowing how much gas you need to get from each gas
: station to the next and how much gas you can get at each station, design an
: algorithm to find the gas station you need to start at to get all the way
: around the circle.
: 跪求各位大神，求思路求解答。

l*82012-08-07 07:08

3 楼

第二题，先不考虑汽车的tank容量。
从任意一个车站A出发，每个车站就加最大可能的油。如果在开往下一站X的过程中油
耗尽，则从X重新出发。如果在油没耗尽情况下回到了出发点，成功找到answer，算法
结束。
如果一直试验出发点，回到了第一个出发点A, 没有answer,算法结束。
O(N)

【在 l*********8 的大作中提到】

: 第一题，先从一个节点开始，按照最大连续和的算法计算。
: 回到第一个节点的时候，如果当前累积和小于等于零，算法结束。
: 否则，再算一轮。
: O(n)算法。
:
: an

l*82012-08-07 07:08

4 楼

快慢指针?

i*72012-08-07 07:08

5 楼

我怎么觉得两个解法都有点不对劲。。
第一个解法你走一遍给我看看怎么能从1 -1 2这个循环体中得到2 1.
第二个解法感觉上是O(N^2）的算法吧

【在 l*********8 的大作中提到】

: 第二题，先不考虑汽车的tank容量。
: 从任意一个车站A出发，每个车站就加最大可能的油。如果在开往下一站X的过程中油
: 耗尽，则从X重新出发。如果在油没耗尽情况下回到了出发点，成功找到answer，算法
: 结束。
: 如果一直试验出发点，回到了第一个出发点A, 没有answer,算法结束。
: O(N)

f*e2012-08-07 07:08

6 楼

两个都是对的。

【在 i*********7 的大作中提到】

:
: 我怎么觉得两个解法都有点不对劲。。
: 第一个解法你走一遍给我看看怎么能从1 -1 2这个循环体中得到2 1.
: 第二个解法感觉上是O(N^2）的算法吧

i*72012-08-07 07:08

7 楼

你的意思是，第一题最多只需要简单的转两轮即可？
第二题怎么看都不像是O(N)的吧？它在不停的尝试出发点啊。

【在 f*****e 的大作中提到】

: 两个都是对的。

l*82012-08-07 07:08

8 楼

第二题，不是每个点都可以做出发点，只有前面累积小于零的点才可以做出发点。

【在 i*********7 的大作中提到】

: 你的意思是，第一题最多只需要简单的转两轮即可？
: 第二题怎么看都不像是O(N)的吧？它在不停的尝试出发点啊。

z*e2012-08-07 07:08

9 楼

1st: find the first item that value<0, use it as pivot, start from the next
node to find the sublist with max value, finish until the node reaches the
pivot again. O(n) time cost.
2nd: the first is that at each station, try to get as much gas as possible,
the main idea is to find one station, starting from that station, there is
always gas left when reach one station. if no gas left for one station, then
start from the next station. if the next station if the 1st station, return
with false.
O(N) time cost

g*e2012-08-07 07:08

10 楼

longway2008还是这么犀利啊

l*82012-08-07 07:08

11 楼

过奖了。我的面试准备还差很多呢。

【在 g*********e 的大作中提到】

: longway2008还是这么犀利啊

S*g2012-08-07 07:08

12 楼

我觉得有点问题
比如说1，－2，3，5，－3，2
按你的方法从1开始算到 2的时候累计和是7 （3，5，－3，2的和）所以要继续算
然后会加上1 所以最大还是8（3，5，－3，2，1）程序就结束了，
可是如果从2开始算最大和是9 （2，1，－2，3，5）
是不是我哪里理解错了？
谢谢！

【在 l*********8 的大作中提到】

r*h2012-08-07 07:08

13 楼

第一道题好像有点问题
-1, 4, -5, 6, 10
最大值应该是 6 + 10 + (-1) + 4
而不是 6 + 10

next
,
then
return

【在 z****e 的大作中提到】

: 1st: find the first item that value<0, use it as pivot, start from the next
: node to find the sublist with max value, finish until the node reaches the
: pivot again. O(n) time cost.
: 2nd: the first is that at each station, try to get as much gas as possible,
: the main idea is to find one station, starting from that station, there is
: always gas left when reach one station. if no gas left for one station, then
: start from the next station. if the next station if the 1st station, return
: with false.
: O(N) time cost

r*h2012-08-07 07:08

14 楼

第一题随意取一个节点，按最大子串和做
结果用{ }表示，分三种情况：
1.
{ a[1] ..... a[k] } a[k+1].........a[n]
以a[k+1]为头节点，再次求最大子串和
2.
a[1] ... { a[p] ... a[q] } ... a[n]
以a[p]或a[q+1]为头节点，再次求最大子串
3.
a[1] ... { a[k] ... a[n] }
以a[k]为头节点，再次就最大子串
请牛人指正

an

【在 i*********7 的大作中提到】

W*n2012-08-07 07:08

15 楼

an
Answer: what a stupid Q.
Don't recommend working for a company with stupid interviewer asking stupid
questions.
hahaha

【在 i*********7 的大作中提到】

W*n2012-08-07 07:08

16 楼

Btw, "circular" linked-list?! What a genius invention!
hahaha

I*82012-08-07 07:08

17 楼

I think circular linked-list is common, just like a single linkedlist, but
the end node's next is not null but head.
For Question 1, My answer is:
First loop from head to next time meeting head, maintain a max and the
references of the start, end points of the sequence.
Then starts from the ending point,loop the linked-list again,maintain two
max value, heading sequence(ending with the start point),tailing sequence(
starting with end point), then use the new sum of three values, and new
start, end point.

【在 W***n 的大作中提到】

: Btw, "circular" linked-list?! What a genius invention!
: hahaha

f*e2012-08-07 07:08

18 楼

按照他的算法第一遍找到(x_L,...,x_M)得到f1
按照他的算法第二遍从x_M开始反向找到(x_M,x_M-1,x_M-2,...,x_T)得到f2
第三遍求(-x_L,...,-x_M)的最大连续和s1。f3=sum(x_1+...+x_n)+s1，这步可以优化。
最终结果=max(f1,f2,f3)
只转一圈也可以搞定,记录2个状态既可（其实也就是对上面三步的总结与简化）：
max_i
sum(x_1+...+x_n)-sum_i+max_i
1, -2, 3, 5,-3, 2, 1,-2
max_i : 1, 1, 3, 8, 8, 8, 8, 8
sum_i : 1, -1, 3, 8, 5, 7, 8, 6
6-sum_i+max_i: 6, 8, 6, 6, 9, 7, 6, 8
max=max{max_i, 6-sum_i+max_i}=9
数学证明很简单，假设存在一个从L到L+n的最大连续和(x_L,...,x_M)，考虑起始点
和终点在不同区域的情形。

【在 S********g 的大作中提到】

: 我觉得有点问题
: 比如说1，－2，3，5，－3，2
: 按你的方法从1开始算到 2的时候累计和是7 （3，5，－3，2的和）所以要继续算
: 然后会加上1 所以最大还是8（3，5，－3，2，1）程序就结束了，
: 可是如果从2开始算最大和是9 （2，1，－2，3，5）
: 是不是我哪里理解错了？
: 谢谢！

q*s2012-08-07 07:08

19 楼

第一题：相当于求2个首尾相接的数字串的最大和子串，前者最少可以O（n），因此
此题也可O（n）。
第二题：假设从任一点start开始，顺时针计算sum。 sum < 0, start--。 sum >0,
继续顺时针计算sum。最后sum>0时候的start即为所求。 O（n）

q*s2012-08-07 07:08

20 楼

你这答案不是O（n）

【在 l*********8 的大作中提到】

: 第二题，不是每个点都可以做出发点，只有前面累积小于零的点才可以做出发点。

D*f2012-08-07 07:08

21 楼

他的答案应该是O（n），如果从点A到X时和小于0，可以证明A与X间任何一点都不能作
为开始点，因为它们到X肯定是负的。

【在 q****s 的大作中提到】

: 你这答案不是O（n）

f*e2012-08-07 07:08

22 楼

他的答案不完整，不能解决某些情况，我给出了标准答案，也只要O(n)。

【在 D**f 的大作中提到】

: 他的答案应该是O（n），如果从点A到X时和小于0，可以证明A与X间任何一点都不能作
: 为开始点，因为它们到X肯定是负的。

D*f2012-08-07 07:08

23 楼

如果第一题给出的是全为正的序列，上面大多数（如果不是所有的）答案都会给出2倍
的和出来。

f*e2012-08-07 07:08

24 楼

没有吧，即使考查sum<0的那个答案都可以完成你这个目标。

【在 D**f 的大作中提到】

: 如果第一题给出的是全为正的序列，上面大多数（如果不是所有的）答案都会给出2倍
: 的和出来。

l*82012-08-07 07:08

25 楼

要加限制，系列长度不能超过节点个数。

【在 D**f 的大作中提到】

: 如果第一题给出的是全为正的序列，上面大多数（如果不是所有的）答案都会给出2倍
: 的和出来。