推荐几支Stem Cell stocks吧. - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

推荐几支Stem Cell stocks吧.

推荐几支Stem Cell stocks吧.# Stock

f*r2008-11-12 08:11

1 楼

今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
题目：
A sequence of numbers is called a zig-zag sequence if the differences betwee
n successive numbers strictly alternate between positive and negative. The f
irst difference (if one exists) may be either positive or negative. A sequen
ce with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3
,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1
,7,4,5,5 are n

v*c2008-11-12 08:11

2 楼

求祝福: 嫂子明天上海二签.
谢谢大家!

b*t2008-11-12 08:11

3 楼

我印象中都不是很贵，属于多年被打压对象，也许傲八上台这些股票的funding都没有
问题了。

x*32008-11-12 08:11

4 楼

没看懂你的解法，
比如这段程序，
if(DiffArray[i]*DiffArray[i+1] < 0)
你只是判断相邻的三个元素是不是zig zag，
但是longest zz subsequence里的元素不一定要相邻
能说下你的subproblem space是什么吗
我的subproblem定义是
给定序列A[1..n]
LCCZ(i) = the length of longest ZZ subsequence ending at A[i]
原题的解LCCZ(A) = max(A[i]) 1<=i<=n

v*52008-11-12 08:11

5 楼

Good Luck!

【在 v******c 的大作中提到】

: 求祝福: 嫂子明天上海二签.
: 谢谢大家!

b*t2008-11-12 08:11

6 楼

我印象中都不是很贵，属于多年被打压对象，也许傲八上台这些股票的funding都没有
问题了。

B*t2008-11-12 08:11

7 楼

想复杂了，这个贪心就可以了, 设置个flag， s[i]>s[i-1]， flag=true,
s[i]flag=true的时候，如果s[i]>=s[i-1],i++ 直到s[i]反之类似。

differences betwee
negative. The f
negative. A sequen
sequence.
differences (6,-3
1,4,7,2,5 and 1
first two differen
zero.

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

: 今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
: 题目：
: A sequence of numbers is called a zig-zag sequence if the differences betwee
: n successive numbers strictly alternate between positive and negative. The f
: irst difference (if one exists) may be either positive or negative. A sequen
: ce with fewer than two elements is trivially a zig-zag sequence.
: For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3
: ,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1
: ,7,4,5,5 are n

j*u2008-11-12 08:11

8 楼

Good luck.

I*S2008-11-12 08:11

9 楼

x*32008-11-12 08:11

10 楼

不是很理解，能run个例子吗

【在 B*****t 的大作中提到】

: 想复杂了，这个贪心就可以了, 设置个flag， s[i]>s[i-1]， flag=true,
: s[i]: flag=true的时候，如果s[i]>=s[i-1],i++ 直到s[i]: 反之类似。
:
: differences betwee
: negative. The f
: negative. A sequen
: sequence.
: differences (6,-3

f*52008-11-12 08:11

11 楼

Good luck.

h*62008-11-12 08:11

12 楼

这是Topcoder上的题吧。
遍历一遍就可以了：
如果当前和前一个相等，则跳过
如果当前应该比前一个大实际也比前一个大，计数加1，标志翻转
如果当前应该比前一个小实际也比前一个小，计数加1，标志翻转
每次循环必须更新当前数和前一个数，仅计数加1的时候标志才翻转。

A*a2008-11-12 08:11

13 楼

Bless

B*t2008-11-12 08:11

14 楼

如 1 3 2 1 4
3>1 flag=true; res = 2;
2<3 flag=!flag; res++;
1<2 continue;
4>1 flag=!flag; res++;
每次flag翻转的时候res++；

【在 x******3 的大作中提到】

: 不是很理解，能run个例子吗

j*u2008-11-12 08:11

15 楼

过了吗

【在 v******c 的大作中提到】

: 求祝福: 嫂子明天上海二签.
: 谢谢大家!

x*32008-11-12 08:11

16 楼

对于第一个数怎么处理
自动计入longest ZZ subsequence吗

【在 h**6 的大作中提到】

: 这是Topcoder上的题吧。
: 遍历一遍就可以了：
: 如果当前和前一个相等，则跳过
: 如果当前应该比前一个大实际也比前一个大，计数加1，标志翻转
: 如果当前应该比前一个小实际也比前一个小，计数加1，标志翻转
: 每次循环必须更新当前数和前一个数，仅计数加1的时候标志才翻转。

d*n2008-11-12 08:11

17 楼

int longestZigZag(int sequence[], int num)
{
// arguments validation skipped
int s= 1;
while (s < num && sequence[s] == sequence[s-1])
s++;
if (s == num ) return 1;
int count = 2;
int increasing = (sequence[s]-sequence[s-1] > 0)?1:-1;
while (s < num)
{
if (increasing*(sequence[s]-sequence[s-1]) < 0)
{
++count;
increasing *= -1;
}
++s;
}
return count;
}

【在 x******3 的大作中提到】

: 对于第一个数怎么处理
: 自动计入longest ZZ subsequence吗

x*32008-11-12 08:11

18 楼

多谢BlueAnt和durbin，终于是想明白了

f*r2008-11-12 08:11

19 楼

谢谢指点，呵呵，大家说的对，
我想错了，总以为longest subsequence要是continuous的序列，
应该是这样简单比较就可以了，还不需要
额外分配空间，谢谢！

【在 B*****t 的大作中提到】

b*j2008-11-12 08:11

20 楼

他的是对的，按照你的改了就错了，呵呵

K*g2008-11-12 08:11

21 楼

这个不需要DP吧？

l*a2008-11-12 08:11

22 楼

大家都想明白了？
这个结果我觉得不正确把。
你的算法是如果当前的状态跟上次的状态不一致，则++
如果一样，则不计数。
这样的话，请看 1，4，3，10，9，8，6 ，7，6，9
差值为 3，-1，7，-1，-1，-1，1，-1，3
当扫描到10/9的时候，与3/10不同还可以++，然后9/8，8/6都是递减，跳过
然后6/7是增加了，按照大家的算法，长度可以++了
可实际上这样的序列就是 1，4，3，10，9，（6）7
其实最后还是两次数值下降，这样的结果应该是不正确的吧
难道我什么地方理解得有问题？
欢迎指正

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

: 谢谢指点，呵呵，大家说的对，
: 我想错了，总以为longest subsequence要是continuous的序列，
: 应该是这样简单比较就可以了，还不需要
: 额外分配空间，谢谢！

y*i2008-11-12 08:11

23 楼

补充下，算法的复杂度为O(n）

d*k2008-11-12 08:11

24 楼

这个算法貌似还有些问题，比如
输入：［3，3，3］
期盼输出：0
实际输出：1

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

: int longestZigZag(int sequence[], int num)
: {
: // arguments validation skipped
: int s= 1;
: while (s < num && sequence[s] == sequence[s-1])
: s++;
: if (s == num ) return 1;
: int count = 2;
: int increasing = (sequence[s]-sequence[s-1] > 0)?1:-1;
: while (s < num)

d*k2008-11-12 08:11

25 楼

我也试试，请指教，C语言风格：
int longestZigZagSequence(int[] s, int size){
if(NULL == s || size < 0){
fprintf(stderr, "Incorrect parameters in longestZigZagSequence(...)!
")
exit(1);
} else if(size < 2) {
return 0;
}
int i;
int flag = 0;
int zzCount = 0;
for(i=1; iif(s[i] == s[i-1]){
continue;
} else if(s[i] > s[i-1] && flag <= 0){
zzCount++;
flag = 1;
} else if(s[i] < s

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

l*a2008-11-12 08:11

26 楼

please use some samples for testing

longestZigZagSequence(...)!

【在 d****k 的大作中提到】

: 我也试试，请指教，C语言风格：
: int longestZigZagSequence(int[] s, int size){
: if(NULL == s || size < 0){
: fprintf(stderr, "Incorrect parameters in longestZigZagSequence(...)!
: ")
: exit(1);
: } else if(size < 2) {
: return 0;
: }
: int i;

y*i2008-11-12 08:11

27 楼

测试下
1 2 1 2 1000 999 1000 999 1000 999 1000

)!

【在 d****k 的大作中提到】

d*k2008-11-12 08:11

28 楼

删除索引为3的元素，剩下的是一个最长的序列

..

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

: 测试下
: 1 2 1 2 1000 999 1000 999 1000 999 1000
:
: )!

x*r2008-11-12 08:11

29 楼

不是很懂你的问题，但我觉得他们的意思是
10->9 ++
9->8 keep
8->6 keep
6->7 ++(这一步没有错，因为你只要放弃之前的9，选这个6，就可以满足zigzag条件）
7->6 ++
6->9 ++
所以我看好像是没错呀

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

: 大家都想明白了？
: 这个结果我觉得不正确把。
: 你的算法是如果当前的状态跟上次的状态不一致，则++
: 如果一样，则不计数。
: 这样的话，请看 1，4，3，10，9，8，6 ，7，6，9
: 差值为 3，-1，7，-1，-1，-1，1，-1，3
: 当扫描到10/9的时候，与3/10不同还可以++，然后9/8，8/6都是递减，跳过
: 然后6/7是增加了，按照大家的算法，长度可以++了
: 可实际上这样的序列就是 1，4，3，10，9，（6）7
: 其实最后还是两次数值下降，这样的结果应该是不正确的吧

y*i2008-11-12 08:11

30 楼

我理解错了，多谢指正！

【在 d****k 的大作中提到】

: 删除索引为3的元素，剩下的是一个最长的序列
:
: ..

K*g2008-11-12 08:11

31 楼

请问你怎么知道放弃前面的9呢，如果按照前面的代码，是不会放弃9的，除非我们加判
断条件。

【在 x****r 的大作中提到】

: 不是很懂你的问题，但我觉得他们的意思是
: 10->9 ++
: 9->8 keep
: 8->6 keep
: 6->7 ++(这一步没有错，因为你只要放弃之前的9，选这个6，就可以满足zigzag条件）
: 7->6 ++
: 6->9 ++
: 所以我看好像是没错呀