f****e
发帖数: 923 | 1 逆序输出一个单链表，要求空间复杂度为O(lgn)，不能修改链表结构（也就是不可以
reverse链表，然后再reverse回去），可以适当牺牲时间复杂度（其实就是O(nlgn)的
意思）
stock follow 可以随便交易很多次，可以同时买很多股票，但是一旦卖就要把手里的
股票全部卖了，问怎样最大化收益。比如[1, 2,3], 前2天都买，第三天全部卖，收益
就是(3-1)+(3-2). | k***a
发帖数: 1199 | 2 第一题典型的divide and conquer, O(n)把链表切成两半,然后分别递归,和quick sort
一样,时间复杂度nlgn,空间lgn
第二题定义不清
【在 f****e 的大作中提到】
: 逆序输出一个单链表，要求空间复杂度为O(lgn)，不能修改链表结构（也就是不可以
: reverse链表，然后再reverse回去），可以适当牺牲时间复杂度（其实就是O(nlgn)的
: 意思）
: stock follow 可以随便交易很多次，可以同时买很多股票，但是一旦卖就要把手里的
: 股票全部卖了，问怎样最大化收益。比如[1, 2,3], 前2天都买，第三天全部卖，收益
: 就是(3-1)+(3-2).
| f****e
发帖数: 923 | 3 谢谢,求代码
sort
【在 k***a 的大作中提到】
: 第一题典型的divide and conquer, O(n)把链表切成两半,然后分别递归,和quick sort
: 一样,时间复杂度nlgn,空间lgn
: 第二题定义不清
| c********t
发帖数: 5706 | 4 我也觉得是这个思路，可是第一切是要改变链表结构的，第二不改变结构，光输出就要
O(n) space存， 难道只是print out吗？
sort
【在 k***a 的大作中提到】
: 第一题典型的divide and conquer, O(n)把链表切成两半,然后分别递归,和quick sort
: 一样,时间复杂度nlgn,空间lgn
: 第二题定义不清
| Y****n
发帖数: 7 | 5 第一题分治不需要修改链表的数据结构。 应该只是打印结果，不用保存结果。
【在 c********t 的大作中提到】
: 我也觉得是这个思路，可是第一切是要改变链表结构的，第二不改变结构，光输出就要
: O(n) space存， 难道只是print out吗？
:
: sort
| c********t
发帖数: 5706 | 6 第二题，找最大值，最大值前面都买，最大值卖，然后recursively 做最大值后面的
array， 代码很好写，就不上了。
【在 f****e 的大作中提到】
: 逆序输出一个单链表，要求空间复杂度为O(lgn)，不能修改链表结构（也就是不可以
: reverse链表，然后再reverse回去），可以适当牺牲时间复杂度（其实就是O(nlgn)的
: 意思）
: stock follow 可以随便交易很多次，可以同时买很多股票，但是一旦卖就要把手里的
: 股票全部卖了，问怎样最大化收益。比如[1, 2,3], 前2天都买，第三天全部卖，收益
: 就是(3-1)+(3-2).
| c********t
发帖数: 5706 | 7 多谢，大概思路如下，细节要推敲一下.
rev( head, tail){
one pass find half, half+1, tail-1;
print tail;
rev(half+1, tail-1);
rev(head, half);
}
【在 Y****n 的大作中提到】
: 第一题分治不需要修改链表的数据结构。 应该只是打印结果，不用保存结果。
|
|
