**结束。**此问题需要详细的调试信息。它目前不接受答案。
**想改进这个问题吗?**更新问题,使其成为堆栈溢出的主题。
4个月前关门了。
改进这个问题
我有一个关于这个问题和我的解决方案的问题。给定三个序列a,b,c-i使用逻辑求每对(a,b),(b,c)和(c,a)的最长公共子序列值。然后找出三者中的最小值。它应该给我们最长的公共子序列值。
我想知道为什么我的解决方案不可靠?下面是我使用的代码(java)。
驱动程序代码:
int result1 = DynamicProgramming.longestCommonSequence(a, b);
int result2 = DynamicProgramming.longestCommonSequence(b, c);
int result3 = DynamicProgramming.longestCommonSequence(c, a);
int temp = Math.min(result1, result2);
System.out.println(Math.min(result3, temp));
程序逻辑:
public static int longestCommonSequence(int[] a, int[] b) {
int[][] aS = new int[a.length + 1][b.length + 1];
int tempAS;
for (int i = 0; i < aS.length; i++)
for (int j = 0; j < aS[0].length; j++) {
if (i == 0) {
aS[i][j] = j;
} else if (j == 0) {
aS[i][j] = i;
} else {
int ins = aS[i][j - 1] + 1;
int del = aS[i - 1][j] + 1;
int mat = aS[i - 1][j - 1];
tempAS = Math.min(ins, del);
if (a[i - 1] == b[j - 1])
aS[i][j] = Math.min(mat, tempAS);
else
aS[i][j] = tempAS;
}
}
return (a.length + b.length - aS[a.length][b.length]) / 2;
}
这个程序适用于我尝试过的所有测试用例。但当我把它提交给在线自动测试仪时,它在最后一个测试用例(edx课程)中失败了。我想不出解决办法会失败的情况。任何帮助都将不胜感激。
我们可以假设所有输入值都是有效整数,数组a、b、c都不是空的。
附言:我已经找到了另外一种通过所有测试的解决方案。但我很想知道我逻辑上的缺陷。谢谢。
1条答案
按热度按时间gz5pxeao1#
如果字符串a是aaaaaaaabbbbb
b串是bbbbbbccccccc
字符串c是ccccccaaaaaaaa
则(a,b)具有长度为7的公共子序列,(b,c)具有长度为7的公共子序列,(c,a)具有长度为7的公共子序列
但是否有一个子序列是所有3个共同的呢(回答:不。。。所以只取3对比较的最小值的想法是有缺陷的)