找出最長序列在一個字符串中的時間長度

Question

我最近在一次採訪中遇到了這個問題，這就是我想出的結果。任何反饋？

找出串中最長序列的長度。例如，字符串「abccdeeeeef」的答案將是5.

static int LongestSeq(string strPass) 
    { 
     int longestSeq = 0; 

     char[] strChars = strPass.ToCharArray(); 

     int numCurrSeq = 1; 
     for (int i = 0; i < strChars.Length - 1; i++) 
     { 
      if (strChars[i] == strChars[i + 1]) 
      { 
       numCurrSeq++; 
      } 
      else 
      { 
       numCurrSeq = 1; 
      } 

      if (longestSeq < numCurrSeq) 
      { 
       longestSeq = numCurrSeq; 
      } 
     } 

     return longestSeq; 
    } 

Answer 1

第一條評論：您不需要將其轉換爲char數組。您可以直接將字符串編入索引。

第二條評論：如果您願意，可以使用foreach並記住「當前」項目，輕鬆將其推廣至IEnumerable<T>。

的第三點意見：我覺得longestSeq和numCurrSeq之間的比較會比較清楚的：

if (numCurrSeq > longestSeq) 

對我來說，這是更自然，因爲我通常有表達的變化部分第一。

Answer 2

這將爲長度爲1的字符串（當它應該返回1）返回0。

Answer 3

你總是可以重寫最後一個字符，所以你不需要在迭代中訪問數組兩次。

在你的循環中，你可以使用另一個迭代循環，只要當前字符與最後一個字符相同。在這個子循環之後，你可以檢查當前的numCurrSeq> longestSeq你是否每次迭代都不需要這個檢查，但是對於每個子序列。

Answer 4

我想補充我的2便士，這是一個使用正則表達式的替代：

string source = "eeabccdeeeeef"; 
Regex reg = new Regex(@"(\w)\1+"); 
MatchCollection matches = reg.Matches(source); 

int longest = 0; 
foreach (System.Text.RegularExpressions.Match match in matches) 
{ 
    if (longest < match.Length) longest = match.Length; 
} 

由於張貼我以前的答案時沒有在第一時間正確讀取的問題，我也許應該加入一些實際的反饋考慮到這是OP發佈的問題。然而，Henrik或者Job Skeet提到了我提出的每一點，所以我只強調Jon Skeet提出的觀點;你不必將字符串轉換爲字符數組，你可以只指數字符串中的特定點如下：

char letter = someString[4]; 

所以，如果你有strPass更換strChars應該都還在工作。

Answer 5

我真的不知道這是什麼的langauge（C＃？），所以請原諒任何輕微的語法毛刺（我不知道這是否是「否則，如果」或「ELSEIF」或「ELIF」或別的什麼）

static int LongestSeq(string strPass) 
{ 
    int longestSeq = 1; 

    int curSeqStart = 0; 
    for (int i = 1; i < strPass.Length; i++) 
    { 
     if (strPass[i] != strPass[curSeq]) 
     { 
      curSeqStart = i; 
     } 
     else if (i - curSeqStart + 1 > longestSeq) 
     { 
      longestSeq = i - curSeqStart + 1; 
     } 
    } 
    return longestSeq; 
} 

這可能是更有效地做

... 
else 
{ 
    len = i - curSeqStart + 1 
    if (len > longestSeq) 
    { 
     longestSeq = len; 
    } 
} 

甚至只是

... 
else 
{ 
    longestSeq = max(longestSeq, i - curSeqStart + 1) 
} 

取決於如何好您的'最大'的實現和編譯器。

Answer 6

我認爲這有效嗎？我不會無意中寫遞歸方法，我會完全想出海報的答案。

public static int recurse(Char last, int seqLength, int currentIndex, int largestSeqLength, string source) 
{ 
    if (currentIndex > source.Length) 
    { 
     return largestSeqLength; 
    } 

    if (source[currentIndex] == last) 
    { 
     seqLength++; 
     if (seqLength > largestSeqLength) 
     { 
      largestSeqLength = seqLength; 
     } 
    } 
    else 
    { 
     seqLength = 1; 
    } 

    return recurse(source[currentIndex], seqLength, currentIndex++, largestSeqLength, source); 
} 

Answer 7

而另一個實現

public static int LongestSeq<T>(this IEnumerable<T> source) 
{ 
    if (source == null) 
     throw new ArgumentNullException("source"); 

    int result = 0; 
    int currentCount = 0; 

    using (var e = source.GetEnumerator()) 
    { 
     var lhs = default(T); 

     if (e.MoveNext()) 
     { 
      lhs = e.Current; 
      currentCount = 1; 
      result = currentCount; 
     } 

     while (e.MoveNext()) 
     { 
      if (lhs.Equals(e.Current)) 
      { 
       currentCount++; 
      } 
      else 
      { 
       currentCount = 1; 
      } 

      result = Math.Max(currentCount, result); 
      lhs = e.Current; 
     } 
    } 

    return result; 
} 

Answer 8

一個簡單的（未經測試）的解決辦法是：

int GetLongestSequence(string input) 
{ 
    char c = 0; 
    int maxSequenceLength = 0; 
    int maxSequenceStart = 0; 
    int curSequenceLength = 0; 
    int length = input.Length; 

    for (int i = 0; i < length; ++i) 
    { 
    if (input[i] == c) 
    { 
     ++curSequenceLength; 
     if (curSequenceLength > maxSequenceLength) 
     { 
     maxSequenceLength = curSequenceLength; 
     maxSequenceStart = i - (curSequenceLength - 1); 
     } 
    } 
    else 
    { 
     curSequenceLength = 1; 
     c = input[i]; 
    } 
    } 
    return maxSequenceStart; 
} 

或者結構更好的代碼（也未經測試）：

private int GetSequenceLength(string input, int start) 
{ 
    int i = start; 
    char c = input[i]; 
    while (input[i] == c) ++i; // Could be written as `while (input[i++] == c);` but i don't recommend that 
    return (i - start); 
} 

public int GetLongestSequence(string input) 
{ 
    int length = input.Length; 
    int maxSequenceLength = 0; 
    int maxSequenceStart = 0; 

    for (int i = 0; i < length; /* no ++i */) 
    { 
    int curSequenceLength = this.GetSequenceLength(input, i); 
    if (curSequenceLength > maxSequenceLength) 
    { 
     maxSequenceLength = curSequenceLength; 
     maxSequenceStart = i; 
    } 
    i += curSequenceLength; 
    } 
    return maxSequenceStart; 
} 

Answer 9

這個擴展方法找到了lon在一個字符串中相同字符的gest序列。

public static int GetLongestSequenceOfSameCharacters(this string sequence) 
     { 
      var data = new List<char>(); 
      for (int i = 0; i < sequence.Length; i++) 
      { 
       if (i > 0 && (sequence[i] == sequence[i - 1])) 
       { 
        data.Add(sequence[i]); 
       }    
      } 

      return data.GroupBy(x => x).Max(x => x.Count()) + 1; 
     } 

[TestMethod] 
     public void TestMethod1() 
     { 
      // Arrange 
      string sequence = "aabbbbccccce"; 

      // Act 
      int containsSameNumbers = sequence.GetLongestSequenceOfSameCharacters(); 

      // Assert 
      Assert.IsTrue(containsSameNumbers == 5); 

     }