Indeks najdłuższego uruchomienia C#

Question

Próbuję rozwiązać to pytanie: Napisz funkcję, która wyszukuje indeks oparty na zera najdłuższego przebiegu w łańcuchu. Bieg to kolejna sekwencja tego samego bohatera. Jeśli jest więcej niż jeden cykl o tej samej długości, zwróć indeks pierwszego.

Na przykład IndexOfLongestRun ("abbcccddddcccbba") powinien powrócić 6 jak najdłuższej perspektywie jest dddd i to po raz pierwszy pojawia się na indeksie 6.

Po co mam zrobić:

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); 
    } 
} 

Problemem jest to, że kiedy dojdę do ostatniego indeksu, na przykład "abbccaaaaaaaaa" , który jest w tym przypadku, i gdy i=14 (biorąc ten ciąg jako przykład) i gdy i<array1.Length-1 jest fałszywe, pętla for przeskoczy bezpośrednio do return indexOf; i zwróci zły indeks , Próbuję dowiedzieć się ho w pchnąć forloop, aby kontynuować implementację, aby idenxOf mógł zostać zmieniony na właściwy indeks. Proszę o pomoc?

Answer 1

Można sprawdzić, czy osiągnięto nowy najlepszy wynik dla każdej iteracji, gdy prąd == poprzedni. Minimalnie wolniejszy, ale pozwala na pisanie kodu krótszy pomijając dodatkowy czek po pętli:

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

Promuj zmienną pętli i do zakresu metody i powtórz blok warunkowy, jeśli (maxCount < licznik) {...} zaraz po wyjściu pętli. W ten sposób, wykonuje jeszcze raz po pętla kończy

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

To zwróci -1 jeśli ciąg jest pusta i trzeba elastyczność powrocie indeks i licznik w zależności od specyfikacji.

 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

Jak zwykle z opóźnieniem, ale dołączył do partii. Naturalny klasyczny algorytm:

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; 
} 

Na końcu masz zarówno najdłuższy indeks, jak i długość.

Answer 5

Zaakceptowanych odpowiedź od Kvam działa świetnie dla małych strun, ale jako długość zbliża 100.000 znaków (i być może nie jest to konieczne), jego Wains efektywności.

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(); 
    } 

To rozwiązanie jest dwa razy szybsze niż Kvam z dużymi ciągami. Możliwe są inne optymalizacje.

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; 
    }