Längste Sequenz der Nummer in zwei Arrays

Question

Ich habe zwei Array, die in einer Zufallszahl zwischen 0-9
initialisieren Ich muss die längste gleiche Sequenz, die in beiden existieren.

Zum Beispiel

var arrFirst = [8,5,3,0,3,1,8,2,8,7,3,5,4,0,8,5,7,3,1] 
var arrSecond = [8,5,4,0,2,9,4,3,6,9,2,3,1,8,2,8,7,3,3] 

Das Ergebnis Array müssen die längste Sequenz enthält, die

var arrResult = [3,1,8,2,8,7,3] 

In diesem Beispiel sowohl Array erscheinen sie Sequenz direkt am Start haben [8, 5], aber es ist nicht der längste.

Könnten Sie bitte einen Code zur Verfügung stellen, der mir helfen würde?

Thanx

Answer 1

Sie ECH Element array1 mit einem while mit jedem Element von array2 und gehen mit der Überprüfung der Elemente überprüfen könnten Schleife mit einem Zähler und für jedes Array einen Offset für den Index.

Später überprüfen, ob die Länge der gefundenen gleichen Elemente größer oder gleich dem zuletzt gefundenen Array ist und entweder die Ergebnismenge durch die neue längere ersetzen oder anhängen, wenn sie gleich der Ergebnismenge ist.

var array1 = [8, 5, 3, 0, 3, 1, 8, 2, 8, 7, 3, 5, 4, 0, 8, 5, 7, 3, 1], 
 
    array2 = [1, 8, 4, 0, 2, 9, 4, 3, 6, 9, 2, 3, 1, 8, 2, 8, 7, 3, 3], 
 
    result = array1.reduce(function (r, _, i, a) { 
 
     array2.forEach(function (__, j, b) { 
 
      var k = 0, 
 
       temp = []; 
 

 
      while ((i + k) in a && (j + k) in b && a[i + k] === b[j + k]) { 
 
       temp.push(a[i + k]); 
 
       k++; 
 
      } 
 
      if (!r.length || temp.length > r[0].length) { 
 
       r = [temp]; 
 
       return; 
 
      } 
 
      if (temp.length === r[0].length) { 
 
       r.push(temp); 
 
      } 
 
     }); 
 
     return r; 
 
    }, []); 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Pseudo-Code:

1)create two more arrays for longest sequence and another one for running sequence 
2)Start looking for matches between 2 original arrays 
3)Keep current sequence in runningSequence array 
4)check if arrays match 
    5)if so check if length of running sequence is longer than theLongestSequence array 
    6)If so, replace the longestSequenceArray content with runningSequence array and keep going 
    7)if not, proceed to next char position 
8)Repeat until all chars in original arrays are processed by going back to step 4 
9)Print Longest array content 

Es ist Ihre Verantwortung, um Code für obige Logik zu schreiben.

Viel Glück.

Answer 3

Verwenden wie diese maximale Länge suchen existieren in der zweiten Array

var arrFirst = [8,5,3,0,3,1,8,2,8,7,3,5,4,0,8,5,7,3,1]; 
 
var arrSecond = [8,5,4,0,2,9,4,3,6,9,2,3,1,8,2,8,7,3,3]; 
 
var firstStr = arrFirst.join(""); 
 
var secondStr = arrSecond.join(""); 
 
var combinations = getCombination(firstStr); 
 
combinations = combinations.sort(function(a, b){ 
 
    return b.length - a.length; 
 
}); 
 
for(var i in combinations){ 
 
    if(secondStr.indexOf(combinations[i]) !== -1){ 
 
    console.log(combinations[i]+" found with length : "+combinations[i].length); 
 
    console.log(combinations[i].split("")); 
 
    break; 
 
    } 
 
} 
 

 
function getCombination(str) { 
 
    var fn = function(active, rest, a) { 
 
     if (!active && !rest) 
 
      return; 
 
     if (!rest) { 
 
      if(firstStr.search(active) !== -1){ 
 
       a.push(active); 
 
      } 
 
     } else { 
 
      fn(active + rest[0], rest.slice(1), a); 
 
      fn(active, rest.slice(1), a); 
 
     } 
 
     return a; 
 
    } 
 
    return fn("", str, []); 
 
}