最长运行C#的索引

本文关键字：索引 运行 | 更新日期: 2023-09-27 18:21:43

我正在努力解决这个问题：编写一个函数，查找字符串中最长游程的从零开始的索引。跑步是同一个字符的连续序列。如果有多个具有相同长度的游程，则返回第一个游程的索引。

例如，IndexOfLongestRun（"abbcccdddcccbba"）应该返回6，因为最长的运行是dddd，并且它首次出现在索引6上。

以下是我所做的：

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

问题是，当我到达最后一个索引时，例如"abbccaaaaaaaa"在这种情况下，它是一个，当i=14（以这个字符串为例）和i<array1.Length-1语句为假时，for循环直接跳到return indexOf;并返回错误的索引，我正试图找出如何推送forloop来继续实现，以便将idenxOf更改为正确的索引。请帮忙吗？

最长运行C#的索引

当current==previor时，您可以检查每个迭代是否获得了新的最佳分数。速度最低，但它允许您通过省略循环后的额外检查来编写较短的代码：

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

将循环变量i提升到方法范围，并在循环退出后立即重复条件块if（maxCount<counter）｛…｝。因此，它在循环完成后再执行一次

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

像往常一样迟到了，但加入了聚会。一种自然的经典算法：

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

最后，你有最长的跑步指数和长度。

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

如果字符串为空，则返回-1，并且您可以根据规范灵活地返回索引和计数。

        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;

Kvam接受的答案非常适合小字符串，但随着长度接近100000个字符（也许不需要），其效率会下降。

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

这种解决方案的速度是Kvam的两倍。也许还有其他优化。

相关文章：