f*******r 发帖数: 1086 | 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 |
x******3 发帖数: 245 | 2 没看懂你的解法,
比如这段程序,
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 |
B*****t 发帖数: 335 | 3 想复杂了,这个贪心就可以了, 设置个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
|
x******3 发帖数: 245 | 4 不是很理解,能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
|
h**6 发帖数: 4160 | 5 这是Topcoder上的题吧。
遍历一遍就可以了:
如果当前和前一个相等,则跳过
如果当前应该比前一个大实际也比前一个大,计数加1,标志翻转
如果当前应该比前一个小实际也比前一个小,计数加1,标志翻转
每次循环必须更新当前数和前一个数,仅计数加1的时候标志才翻转。 |
B*****t 发帖数: 335 | 6 如 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个例子吗
|
x******3 发帖数: 245 | 7 对于第一个数怎么处理
自动计入longest ZZ subsequence吗
【在 h**6 的大作中提到】 : 这是Topcoder上的题吧。 : 遍历一遍就可以了: : 如果当前和前一个相等,则跳过 : 如果当前应该比前一个大实际也比前一个大,计数加1,标志翻转 : 如果当前应该比前一个小实际也比前一个小,计数加1,标志翻转 : 每次循环必须更新当前数和前一个数,仅计数加1的时候标志才翻转。
|
d****n 发帖数: 233 | 8 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******3 发帖数: 245 | 9 多谢BlueAnt和durbin, 终于是想明白了 |
f*******r 发帖数: 1086 | 10 谢谢指点,呵呵,大家说的对,
我想错了,总以为longest subsequence要是continuous的序列,
应该是这样简单比较就可以了,还不需要
额外分配空间,谢谢!
【在 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
|
|
|
b****j 发帖数: 78 | |
K******g 发帖数: 1870 | |
l*****a 发帖数: 14598 | 13 大家都想明白了?
这个结果我觉得不正确把。
你的算法是如果当前的状态跟上次的状态不一致,则++
如果一样,则不计数。
这样的话,请看 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*****i 发帖数: 727 | |
d****k 发帖数: 41 | 15 这个算法貌似还有些问题,比如
输入:[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****k 发帖数: 41 | 16 我也试试,请指教,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; i
if(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 的大作中提到】 : 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)
|
l*****a 发帖数: 14598 | 17 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*****i 发帖数: 727 | 18 测试下
1 2 1 2 1000 999 1000 999 1000 999 1000
)!
【在 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;
|
d****k 发帖数: 41 | 19 删除索引为3的元素,剩下的是一个最长的序列
..
【在 y*****i 的大作中提到】 : 测试下 : 1 2 1 2 1000 999 1000 999 1000 999 1000 : : )!
|
x****r 发帖数: 99 | 20 不是很懂你的问题,但我觉得他们的意思是
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*****i 发帖数: 727 | 21 我理解错了,多谢指正!
【在 d****k 的大作中提到】 : 删除索引为3的元素,剩下的是一个最长的序列 : : ..
|
K******g 发帖数: 1870 | 22 请问你怎么知道放弃前面的9呢,如果按照前面的代码,是不会放弃9的,除非我们加判
断条件。
【在 x****r 的大作中提到】 : 不是很懂你的问题,但我觉得他们的意思是 : 10->9 ++ : 9->8 keep : 8->6 keep : 6->7 ++(这一步没有错,因为你只要放弃之前的9,选这个6,就可以满足zigzag条件) : 7->6 ++ : 6->9 ++ : 所以我看好像是没错呀
|