如何找到最长公共子阵

这里是我的问题：我在JavaScript中5门阵列这样的整数：如何找到最长公共子阵

array1 = [0, 1, 2, 3, 4]; 
array2 = [9, 1, 2, 3, 4]; 
array3 = [10, 1, 2, 11, 4]; 
array4 = [12, 1, 2, 13, 4]; 
array5 = [14, 1, 2, 15, 4];

我必须找到最长公共子阵。在这种情况下，我不得不像这样检索一个数组：[1, 2, 4]。

对于记录，我不会在数组中找到重复，我的主要目标不是执行速度。

感谢

来源

2012-11-29 rikpg

'array1 = [0，1，2，3，4];'（方括号不是圆括号）可能以您期望的方式加载数组。 –

阵列从哪里来？有可能有更好的方式来动态加入它们。这是功课吗？ –

@JimBlackler：我刚刚写下了数组的内容:) – rikpg

试试这个：

var array1 = [0, 1, 2, 3, 4]; 
var array2 = [9, 1, 2, 3, 4]; 
var array3 = [10, 1, 2, 11, 4]; 
var array4 = [12, 1, 2, 13, 4]; 
var array5 = [14, 1, 2, 15, 4]; 

// join everything into one array 
var all = array1.join(',')+','+array2.join(',')+','+array3.join(',')+','+array4.join(',')+','+array5.join(','); 
all = all.split(','); 

// get an object with all unique numbers as keys 
var keys = {}; 
for(var i=0; i<all.length; i++) keys[all[i]] = 1; 
console.log(keys); 

// generate an array with values present in all arrays 
var common = []; 
for(var x in keys) { 
    if(array1.indexOf(parseInt(x)) != -1 && array2.indexOf(parseInt(x)) != -1 && array3.indexOf(parseInt(x)) != -1 && array4.indexOf(parseInt(x)) != -1 && array5.indexOf(parseInt(x)) != -1) { 
    common.push(x); 
    } 
} 
console.log(common);

来源

2012-11-29 15:10:49 techfoobar

当你添加对象到普通数组时，你总是在同一个数组（array1）上执行检查。除此之外它完美地工作！ :) – rikpg

ahh ...错字:-)很高兴的工作。 – techfoobar

我想这可以给你一个良好的开端：我的脚本将返回每个元素的个数的对象。但现在，它将第一个数组作为基础。

var array1 = [0, 1, 2, 3, 4]; 
var array2 = [9, 1, 2, 3, 4]; 
var array3 = [10, 1, 2, 11, 4]; 
var array4 = [12, 1, 2, 13, 4]; 
var array5 = [14, 1, 2, 15, 4]; 
var array6 = [13, 1, 2, 18, 4]; 

var mainArr = [array1, array2, array3, array4, array5, array6] 

function getCommonElement(arr){ 
    var subLength = arr[0].length; 
    var resultArr = new Array(); 
    var ret = new Object(); 
    for(var k=0;k<subLength;k++){ 
     var temp = new Array(); 
     for(var i=0;i<arr.length;i++){ 
      temp.push(arr[i][k]); 
     } 
     resultArr.push(temp); 
    } 
    for(var i=0;i<arr[0].length;i++){ 
     ret[arr[0][i]+''] = resultArr[i].join('').split(arr[0][i]+'').length - 1; 
    } 
    return ret; 
}

干杯。

来源

2012-11-29 15:34:18

#define MAX(a,b) a>b?a:b 

int main(int argc, char* argv[]) 
{ 
     if(argc < 2) 
       return -1; 

     int x = strlen(argv[1])+1; 
     int y = strlen(argv[2])+1; 

     int i,j,k,l; 

     int longest =0; 
     char* LCS = (char*)malloc(sizeof(char)*MAX(x,y)); 

     int** arr = (int**)malloc(sizeof(int*)*x); 

     for(i=0;i<=y;i++) 
     arr[i] =(int*) malloc(sizeof(int)*y); 

     for(i=0;i<=x;i++) 
      for(j=0;j<=y;j++) 
      { 
       arr[i][j] = 0; 
      } 

     for(i=0;i<x;i++) 
       for(j=0;j<y;j++) 
       { 
         if(argv[1][i] == argv[2][j]) 
           arr[i+1][j+1] = arr[i][j]+1; 
         if(arr[i+1][j+1] > longest) 
         { 
           longest =arr[i+1][j+1]; 
           memset(LCS,0,MAX(x,y)); 
           for(k=0,l=i;k<=longest;k++,l--) 
             LCS[k] = argv[1][l]; 

         } 
       } 

     printf(" %s",argv[2]); 
     for(i=0;i<x;i++) 
     { 
       printf("\n%c",argv[1][i]);    
       for(j=0;j<y;j++) 
       { 
       printf("%d",arr[i][j]);                     
       } 
     } 

     printf("\nLongest Common Subarray : %s\n",LCS); 
     return 0; 
}

来源

2013-08-02 09:32:37

如何找到最长公共子阵

回答

相关问题