Index der längsten Lauf C#

Question

Ich versuche, diese Frage zu lösen: Schreiben Sie eine Funktion, die den Null-basierten Index des längsten Laufs in einer Zeichenfolge findet. Ein Lauf ist eine fortlaufende Sequenz desselben Zeichens. Wenn es mehr als einen Lauf mit der gleichen Länge gibt, geben Sie den Index des ersten zurück.

Zum Beispiel IndexOfLongestRun ("abbcccddddcccbba") sollte 6 als längste Abfahrt Rückkehr ist dddd und es erscheint zuerst auf Index 6.

Nach was ich getan habe:

private static int IndexOfLongestRun(string str) 
    { 
     char[] array1 = str.ToCharArray(); 
     //Array.Sort(array1); 
     Comparer comparer = new Comparer(); 
     int counter =1; 
     int maxCount = 0; 
     int idenxOf = 0; 

     for (int i =0; i<array1.Length-1 ; i++) 
     { 
      if (comparer.Compare(array1[i],array1[i+1]) == 0) 
      { 
       counter++; 
      } 
      else { 
       if(maxCount < counter) 
       { 
        maxCount = counter; 
        idenxOf = i - counter + 1; 
       } 
       counter = 1; 
      } 
     } 
     return idenxOf ; 
    } 
} 

public class Comparer : IComparer<char> 
{ 
    public int Compare(char firstChar, char nextChar) 
    { 
     return firstChar.CompareTo(nextChar); 
    } 
} 

Das Problem ist, dass, wenn ich zum letzten Index zum Beispiel "abbccaaaaaaaaaa" , die in diesem Fall ist, und wenn i=14 (nimmt diese Zeichenfolge als Beispiel) und wenn i<array1.Length-1 Statment ist falsch, die for-Schleife springt direkt auf return indexOf; und den falschen Index zurück Ich versuche herauszufinden, ho w, um den Forloop zu forcieren, um die Implementierung fortzusetzen, damit idnxOf in den richtigen Index geändert werden kann. Irgendwelche Hilfe bitte?

Answer 1

Sie können überprüfen, ob für jede Iteration ein neuer bester Score erreicht wird, wenn current == previous. Minimal langsamer, aber es ermöglicht Ihnen kürzeren Code zu schreiben, indem eine zusätzliche Überprüfung nach der Schleife Weglassen:

int IndexOfLongestRun(string input) 
{ 
    int bestIndex = 0, bestScore = 0, currIndex = 0; 
    for (var i = 0; i < input.Length; ++i) 
    { 
     if (input[i] == input[currIndex]) 
     { 
      if (bestScore < i - currIndex) 
      { 
       bestIndex = currIndex; 
       bestScore = i - currIndex; 
      } 
     } 
     else 
     { 
      currIndex = i; 
     } 
    } 
    return bestIndex; 
} 

Answer 2

Fördern die Schleifenvariable i auf Verfahren Umfang und wiederholen den Bedingungsblock if (maxCount < Zähler) {...} direkt nach dem Schleifenausgang. Somit führt es ein weiteres Mal, nachdem die Schleife

private static int IndexOfLongestRun(string str) 
{ 
    char[] array1 = str.ToCharArray(); 
    //Array.Sort(array1); 
    Comparer comparer = new Comparer(); 
    int counter = 1; 
    int maxCount = 0; 
    int idenxOf = 0; 

    int i; 
    for (i = 0; i < array1.Length - 1; i++) 
    { 
     if (comparer.Compare(array1[i], array1[i + 1]) == 0) 
     { 
      counter++; 
     } 
     else 
     { 
      if (maxCount < counter) 
      { 
       maxCount = counter; 
       idenxOf = i - counter + 1; 
      } 
      counter = 1; 
     } 
    } 
    if (maxCount < counter) 
    { 
     maxCount = counter; 
     idenxOf = i - counter + 1; 
    } 
    return idenxOf; 
} 

Answer 3

vervollständigt Dies wird -1 zurück, wenn die Zeichenfolge leer ist, und Sie haben die Flexibilität, den Index zurückkehrt und die Zählung auf Ihrer Spezifikation abhängig.

 string myStr = "aaaabbbbccccccccccccdeeeeeeeee"; 

     var longestIndexStart = -1; 
     var longestCount = 0; 
     var currentCount = 1; 
     var currentIndexStart = 0; 

     for (var idx = 1; idx < myStr.Length; idx++) 
     { 
      if (myStr[idx] == myStr[currentIndexStart]) 
       currentCount++; 
      else 
      { 
       if (currentCount > longestCount) 
       { 
        longestIndexStart = currentIndexStart; 
        longestCount = currentCount; 
       } 

       currentIndexStart = idx; 
       currentCount = 1; 
      } 
     } 

     return longestIndexStart; 

Answer 4

Wie üblich spät, aber der Beitritt zur Partei. Ein natürlicher klassischer Algorithmus:

static int IndexOfLongestRun(string input) 
{ 
    int longestRunStart = -1, longestRunLength = 0; 
    for (int i = 0; i < input.Length;) 
    { 
     var runValue = input[i]; 
     int runStart = i; 
     while (++i < input.Length && input[i] == runValue) { } 
     int runLength = i - runStart; 
     if (longestRunLength < runLength) 
     { 
      longestRunStart = runStart; 
      longestRunLength = runLength; 
     } 
    } 
    return longestRunStart; 
} 

Am Ende haben Sie beide längste Lauf Index und Länge.

Answer 5

Die akzeptierte Antwort von Kvam funktioniert gut für kleine Strings, aber wenn die Länge 100.000 Zeichen erreicht (und vielleicht wird dies nicht benötigt), ist ihre Effizienz verloren.

public static int IndexOfLongestRun(string str) 
    { 
     Dictionary<string, int> letterCount = new Dictionary<string, int>(); 

     for (int i = 0; i < str.Length; i++) 
     { 
      string c = str.Substring(i, 1);      

      if (letterCount.ContainsKey(c)) 

       letterCount[c]++; 
      else 

       letterCount.Add(c, 1); 
     } 

     return letterCount.Values.Max(); 
    } 

Diese Lösung ist doppelt so schnell wie Kvam mit großen Saiten. Es gibt vielleicht andere Optimierungen.

Answer 6

public static int IndexOfLongestRun(string str) 
    { 
     var longestRunCount = 1; 
     var longestRunIndex = 0; 
     var isNew = false; 

     var dic = new Dictionary<int, int>(); 

     for (var i = 0; i < str.Length - 1; i++) 
     { 
      if (str[i] == str[i + 1]) 
      { 
       if (isNew) longestRunIndex = i; 
       longestRunCount++; 
       isNew = false; 
      } 
      else 
      { 
       isNew = true; 
       dic.Add(longestRunIndex, longestRunCount); 
       longestRunIndex = 0; 
       longestRunCount = 1; 
      } 
     } 

     return dic.OrderByDescending(x => x.Value).First().Key; 
    }