大喜大悲后据说能开出一朵花---！# Heart - 心情好么？
s*1
1 楼
上个月签了国内一teaching school的合约，之后才来一个心仪的跨国公司industry
interview, 现居住城市的office，真是郁闷啊！要人家要我的话，锯掉国内的，太没
人品了，也断了以后的academic路了。。。
interview, 现居住城市的office，真是郁闷啊！要人家要我的话，锯掉国内的，太没
人品了，也断了以后的academic路了。。。
r*7
2 楼
比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列
R*n
3 楼
说说效果？
http://shop.leapfrog.com/leapfrog/jump/Tag-Readers/category/cat70009?
q_docSort=&addFacet=9004%3Acat70009
http://shop.leapfrog.com/leapfrog/jump/Tag-Readers/category/cat70009?
q_docSort=&addFacet=9004%3Acat70009
x*b
4 楼
那朵花的名字叫做：无所谓！
世界上一些让人大喜大悲的事情，随着一个叫做时间的东西会变成往事。
人对于自己希望发生的事情，对它的期待值会很高。
但世上之事，并非事事尽如人意。对于一件事情期望过高，一旦事情失败之后，他的失
望也就会达到一定的悲伤程度，人如果经常处于失望的状态，在那种情形之下在心间反
而会开出一朵洁白的花朵，那朵花的名字就叫做-----无谓之花
无谓之花其实是对于所有的事情一视同仁，不悲剧、不喜泣。那是一种平静。
其实所有的安慰都没有自己把事情看透彻，来的更有效。
世界上一些让人大喜大悲的事情，随着一个叫做时间的东西会变成往事。
人对于自己希望发生的事情，对它的期待值会很高。
但世上之事，并非事事尽如人意。对于一件事情期望过高，一旦事情失败之后，他的失
望也就会达到一定的悲伤程度，人如果经常处于失望的状态，在那种情形之下在心间反
而会开出一朵洁白的花朵，那朵花的名字就叫做-----无谓之花
无谓之花其实是对于所有的事情一视同仁，不悲剧、不喜泣。那是一种平静。
其实所有的安慰都没有自己把事情看透彻，来的更有效。
f*h
5 楼
面试而已。到给你 offer 的时候再纠结吧。
a*s
6 楼
求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
t*r
7 楼
刚开始的时候会热乎两天，很快就放一边了。也许看小孩儿，我们家的好像没太大作用。
【在 R*****n 的大作中提到】
: 说说效果？
: http://shop.leapfrog.com/leapfrog/jump/Tag-Readers/category/cat70009?
: q_docSort=&addFacet=9004%3Acat70009
【在 R*****n 的大作中提到】
: 说说效果？
: http://shop.leapfrog.com/leapfrog/jump/Tag-Readers/category/cat70009?
: q_docSort=&addFacet=9004%3Acat70009
x*b
8 楼
那朵花的名字叫做：无所谓！
世界上一些让人大喜大悲的事情，随着一个叫做时间的东西会变成往事。
人对于自己希望发生的事情，对它的期待值会很高。
但世上之事，并非事事尽如人意。对于一件事情期望过高，一旦事情失败之后，他的失
望也就会达到一定的悲伤程度，人如果经常处于失望的状态，在那种情形之下在心间反
而会开出一朵洁白的花朵，那朵花的名字就叫做-----无谓之花
无谓之花其实是对于所有的事情一视同仁，不悲剧、不喜泣。那是一种平静。
其实所有的安慰都没有自己把事情看透彻，来的更有效。
世界上一些让人大喜大悲的事情，随着一个叫做时间的东西会变成往事。
人对于自己希望发生的事情，对它的期待值会很高。
但世上之事，并非事事尽如人意。对于一件事情期望过高，一旦事情失败之后，他的失
望也就会达到一定的悲伤程度，人如果经常处于失望的状态，在那种情形之下在心间反
而会开出一朵洁白的花朵，那朵花的名字就叫做-----无谓之花
无谓之花其实是对于所有的事情一视同仁，不悲剧、不喜泣。那是一种平静。
其实所有的安慰都没有自己把事情看透彻，来的更有效。
m*r
9 楼
国内什么样的学校叫Teaching School呀？
★ 发自iPhone App: ChineseWeb 7.3.1
【在 s*****1 的大作中提到】
: 上个月签了国内一teaching school的合约，之后才来一个心仪的跨国公司industry
: interview, 现居住城市的office，真是郁闷啊！要人家要我的话，锯掉国内的，太没
: 人品了，也断了以后的academic路了。。。
★ 发自iPhone App: ChineseWeb 7.3.1
【在 s*****1 的大作中提到】
: 上个月签了国内一teaching school的合约，之后才来一个心仪的跨国公司industry
: interview, 现居住城市的office，真是郁闷啊！要人家要我的话，锯掉国内的，太没
: 人品了，也断了以后的academic路了。。。
r*7
10 楼
linear time 怎么找？
【在 a**********s 的大作中提到】
: 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
【在 a**********s 的大作中提到】
: 求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
d*m
11 楼
杨坤，无所谓
T*a
12 楼
以教学为主的吧
比如南京工程学院（从前的电力高专）
【在 m******r 的大作中提到】
: 国内什么样的学校叫Teaching School呀？
:
: ★ 发自iPhone App: ChineseWeb 7.3.1
h*i
13 楼
是求所有单调升子序列还是一个就行啊
如果一个子序列就行的话，那就是linear阿，贪心法就行。
【在 r********7 的大作中提到】
: linear time 怎么找？
如果一个子序列就行的话，那就是linear阿，贪心法就行。
【在 r********7 的大作中提到】
: linear time 怎么找？
d*m
14 楼
当年第一次听到这首歌
r*7
15 楼
一个就行。
假设 X=[0,2,0,4,3,1,5,0];
Y sorted by X = [0,0,0,1,2,3,4,5]
如何greedy求LCS？
【在 h*********i 的大作中提到】
: 是求所有单调升子序列还是一个就行啊
: 如果一个子序列就行的话，那就是linear阿，贪心法就行。
假设 X=[0,2,0,4,3,1,5,0];
Y sorted by X = [0,0,0,1,2,3,4,5]
如何greedy求LCS？
【在 h*********i 的大作中提到】
: 是求所有单调升子序列还是一个就行啊
: 如果一个子序列就行的话，那就是linear阿，贪心法就行。
d*m
16 楼
觉得太难听了
h*i
17 楼
就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
序列了。。。
【在 r********7 的大作中提到】
: 一个就行。
: 假设 X=[0,2,0,4,3,1,5,0];
: Y sorted by X = [0,0,0,1,2,3,4,5]
: 如何greedy求LCS？
前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
序列了。。。
【在 r********7 的大作中提到】
: 一个就行。
: 假设 X=[0,2,0,4,3,1,5,0];
: Y sorted by X = [0,0,0,1,2,3,4,5]
: 如何greedy求LCS？
h*i
18 楼
好像不用求lcs lcs怎么也得用到dp把，那样就不是线形了。
r*7
19 楼
这个会不会有问题，比方说X=[3,2,1,0,1,2]
线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
但正确结果因该是[0,1,2]
【在 h*********i 的大作中提到】
: 就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
: 前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
: 最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
: 序列了。。。
线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
但正确结果因该是[0,1,2]
【在 h*********i 的大作中提到】
: 就是线形由左至右扫描。。。总是保留当前序列最大值。。然后看下一个元素是否比当
: 前序列中最大值大。。如果有比这个最大值大的就把这个元素加入子序列如果没有这个
: 最大值大就跳过但前元素再往下看。一直到所有元素都被扫描完。这样就是一格单调升
: 序列了。。。
p*a
20 楼
用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]
有多长就行了。
d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
举个例子，假如序列为 2 5 3 4, 则d数列如下
2
2 5
2 3
2 3 4
最后，d的长度为3，LIS is 3。
不过，最后的d不一定是最长上升子序列的答案。
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
有多长就行了。
d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
举个例子，假如序列为 2 5 3 4, 则d数列如下
2
2 5
2 3
2 3 4
最后，d的长度为3，LIS is 3。
不过，最后的d不一定是最长上升子序列的答案。
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
j*h
21 楼
1. number all the element in the original array, in growing sequence (O(n)).
e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
(2,1),(1,2),(0,3),(1,4),(2,5)].
the "number" of each element is the corresponding position it is in the
original array.
2. after numbering, sort the new array according to their original value ,
using quicksort. (O(nlogn))
e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
position" of each element here).
3. find the lo
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
(2,1),(1,2),(0,3),(1,4),(2,5)].
the "number" of each element is the corresponding position it is in the
original array.
2. after numbering, sort the new array according to their original value ,
using quicksort. (O(nlogn))
e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
position" of each element here).
3. find the lo
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
h*i
22 楼
对需要一些改进
如果结果只有一个元素
可以线形扫描看整个序列是不是单调减，如果是自然单调升就是一个元素
如果不是就把违反单调减的那两个元素拿出来
作为初始的字序列的前两项就好了
。。。。。。。。。就是一个单调升
这样也是合乎题意的，不过感觉这样做就没什么意思了。
我觉得如果问最长单调升子序列查找更有意义，是不是
应该是最长单调升序列查找阿。
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
如果结果只有一个元素
可以线形扫描看整个序列是不是单调减，如果是自然单调升就是一个元素
如果不是就把违反单调减的那两个元素拿出来
作为初始的字序列的前两项就好了
。。。。。。。。。就是一个单调升
这样也是合乎题意的，不过感觉这样做就没什么意思了。
我觉得如果问最长单调升子序列查找更有意义，是不是
应该是最长单调升序列查找阿。
【在 r********7 的大作中提到】
: 这个会不会有问题，比方说X=[3,2,1,0,1,2]
: 线形由左至右扫描。。。总是保留当前序列最大值，那么就是[3]
: 但正确结果因该是[0,1,2]
g*y
23 楼
3跟本问题难道不是等价的？？？
).
),
【在 j*********h 的大作中提到】
: 1. number all the element in the original array, in growing sequence (O(n)).
: e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
: (2,1),(1,2),(0,3),(1,4),(2,5)].
: the "number" of each element is the corresponding position it is in the
: original array.
: 2. after numbering, sort the new array according to their original value ,
: using quicksort. (O(nlogn))
: e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
: position" of each element here).
: 3. find the lo
).
),
【在 j*********h 的大作中提到】
: 1. number all the element in the original array, in growing sequence (O(n)).
: e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
: (2,1),(1,2),(0,3),(1,4),(2,5)].
: the "number" of each element is the corresponding position it is in the
: original array.
: 2. after numbering, sort the new array according to their original value ,
: using quicksort. (O(nlogn))
: e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
: position" of each element here).
: 3. find the lo
g*y
24 楼
你只维护一个数组，肯定是不对的
eg，4 5 6 1 2 3 4
f
【在 p*********a 的大作中提到】
: 用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]
: 有多长就行了。
: d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
: 举个例子，假如序列为 2 5 3 4, 则d数列如下
: 2
: 2 5
: 2 3
: 2 3 4
: 最后，d的长度为3，LIS is 3。
eg，4 5 6 1 2 3 4
f
【在 p*********a 的大作中提到】
: 用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]
: 有多长就行了。
: d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
: 举个例子，假如序列为 2 5 3 4, 则d数列如下
: 2
: 2 5
: 2 3
: 2 3 4
: 最后，d的长度为3，LIS is 3。
p*a
25 楼
一般来LIS只需要求出长度, 这个方法足够了, 我强调了d的结果并不是最后要求的LIS.
【在 g*******y 的大作中提到】
: 你只维护一个数组，肯定是不对的
: eg，4 5 6 1 2 3 4
:
: f
【在 g*******y 的大作中提到】
: 你只维护一个数组，肯定是不对的
: eg，4 5 6 1 2 3 4
:
: f
s*i
26 楼
不可以sort吧。假设4,5,6,1,2,3，最长子列是4,5,6或者1,2,3，你sort了之后不就变
成1,2,3,4,5,6了。。。
这个用DP好了
成1,2,3,4,5,6了。。。
这个用DP好了
j*h
27 楼
no.
in step3 , all elements have already been sorted.
for example,
[3,2,1,0,1,2]->[0,1,1,2,2,3]
actually, if I write out each element in the format (value, position), the
above will become
[(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
)].
in the resulting array, when scanning, you will get (0,4) first, put it in
resulting queue 1.
then you get (1,3), since (3<4),you will dump (0,4), put (1,3) in queue 1
then you get (1,5), keep it in queue1.. since 5>3
then you
【在 g*******y 的大作中提到】
: 3跟本问题难道不是等价的？？？
:
: ).
: ),
in step3 , all elements have already been sorted.
for example,
[3,2,1,0,1,2]->[0,1,1,2,2,3]
actually, if I write out each element in the format (value, position), the
above will become
[(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
)].
in the resulting array, when scanning, you will get (0,4) first, put it in
resulting queue 1.
then you get (1,3), since (3<4),you will dump (0,4), put (1,3) in queue 1
then you get (1,5), keep it in queue1.. since 5>3
then you
【在 g*******y 的大作中提到】
: 3跟本问题难道不是等价的？？？
:
: ).
: ),
j*h
28 楼
the reason not to dump (2,2) is that we already have 2 elements in queue2,
in this case, if you dump 2 elements in exchange for 1 element, it would be
worse.
the
,1
in
【在 j*********h 的大作中提到】
: no.
: in step3 , all elements have already been sorted.
: for example,
: [3,2,1,0,1,2]->[0,1,1,2,2,3]
: actually, if I write out each element in the format (value, position), the
: above will become
: [(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
: )].
: in the resulting array, when scanning, you will get (0,4) first, put it in
: resulting queue 1.
in this case, if you dump 2 elements in exchange for 1 element, it would be
worse.
the
,1
in
【在 j*********h 的大作中提到】
: no.
: in step3 , all elements have already been sorted.
: for example,
: [3,2,1,0,1,2]->[0,1,1,2,2,3]
: actually, if I write out each element in the format (value, position), the
: above will become
: [(3,1),(2,2) ,(1,3),(0,4),(1,5),(2,6)]->[(0,4),(1,3),(1,5),(2,2) ,(2,6),(3,1
: )].
: in the resulting array, when scanning, you will get (0,4) first, put it in
: resulting queue 1.
z*y
29 楼
public static int MCSS(int [] a) {
int max = 0, sum = 0, start = 0, end = 0, i=0;
// Cycle through all possible end indexes.
for (j = 0; j < a.length; j++) {
sum += a[j]; // No need to re-add all values.
if (sum > max) {
max = sum;
start = i; // Although method doesn't return these
end = j; // they can be computed.
}
else if (sum < 0) {
i = j+1; // Only possible MCSSs start with an index >j.
s
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
int max = 0, sum = 0, start = 0, end = 0, i=0;
// Cycle through all possible end indexes.
for (j = 0; j < a.length; j++) {
sum += a[j]; // No need to re-add all values.
if (sum > max) {
max = sum;
start = i; // Although method doesn't return these
end = j; // they can be computed.
}
else if (sum < 0) {
i = j+1; // Only possible MCSSs start with an index >j.
s
【在 r********7 的大作中提到】
: 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
: 我的解法是sort this sequence X to Y, Get the LCS of X and Y.
: Time = O(nlogn + n^2) = O(N^2)
: 对方说还能更快。谁知道该怎么改进？
: Updated: 我忘了说了，是求*最长*单调上升子列
y*g
30 楼
你这个是什么?
【在 z********y 的大作中提到】
: public static int MCSS(int [] a) {
: int max = 0, sum = 0, start = 0, end = 0, i=0;
: // Cycle through all possible end indexes.
: for (j = 0; j < a.length; j++) {
: sum += a[j]; // No need to re-add all values.
: if (sum > max) {
: max = sum;
: start = i; // Although method doesn't return these
: end = j; // they can be computed.
: }
【在 z********y 的大作中提到】
: public static int MCSS(int [] a) {
: int max = 0, sum = 0, start = 0, end = 0, i=0;
: // Cycle through all possible end indexes.
: for (j = 0; j < a.length; j++) {
: sum += a[j]; // No need to re-add all values.
: if (sum > max) {
: max = sum;
: start = i; // Although method doesn't return these
: end = j; // they can be computed.
: }
z*y
32 楼
haha
看错了。这个可以用suffix tree做吧
【在 y*******g 的大作中提到】
: 你这个是什么?
看错了。这个可以用suffix tree做吧
【在 y*******g 的大作中提到】
: 你这个是什么?
c*f
33 楼
mark
d*j
34 楼
...这道题是非常经典的算法题了，网上讨论的有很多，大家应该记住（我也忘了，貌似2年前看到的了）。google: "nlogn的最长子序列算法"
我把答案和分析zz到这里吧(具体的代码网上自己搜):
这是一个很好的题目。题目的算法还是比较容易看出来的，就是求最长上升子序列的长
度。不过这一题的数据规模最大可以达到40000，经典的O(n^2)的动态规划算法明显会
超时。我们需要寻找更好的方法来解决是最长上升子序列问题。
先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1
到i这一段中以i结尾的最长上升子序列的长度，初始时设F[i] = 0(i = 1, 2, ...,
len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且
A[j] < A[i])。
现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < I (2)A[x] < A[y] < A[i] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到
我把答案和分析zz到这里吧(具体的代码网上自己搜):
这是一个很好的题目。题目的算法还是比较容易看出来的，就是求最长上升子序列的长
度。不过这一题的数据规模最大可以达到40000，经典的O(n^2)的动态规划算法明显会
超时。我们需要寻找更好的方法来解决是最长上升子序列问题。
先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1
到i这一段中以i结尾的最长上升子序列的长度，初始时设F[i] = 0(i = 1, 2, ...,
len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且
A[j] < A[i])。
现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < I (2)A[x] < A[y] < A[i] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到
相关阅读