找出最长序列在一个字符串中的时间长度

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

     }