最长索引运行 C#

Question

我正在尝试解决这个问题：编写一个函数，查找字符串中最长运行的从零开始的索引。运行是相同字符的连续序列。如果有多个运行相同长度，return第一个的索引。

例如，IndexOfLongestRun("abbcccddddcccbba") 应该 return 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);
    }
}

问题是当我到达最后一个索引时 "abbccaaaaaaaaaa" 在这种情况下是a，当i=14（以这个字符串为例）和当i<array1.Length-1语句为假时，for循环直接跳转到return indexOf;和return错误的索引，我试图找出如何推动 forloop 继续执行，以便 idenxOf 可以更改为正确的索引。有什么帮助吗？

Answer 1

将循环变量 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;
}

Answer 2

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

        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 3

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

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 4

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

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

最后你有最长的运行索引和长度。

Answer 5

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

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 的两倍。也许还有其他优化。

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

最长索引运行 C#

Index Of Longest Run C#

c#

algorithm

icomparer

最长索引 运行 C#

Index Of Longest Run C#

c#

algorithm

icomparer

最长索引运行 C#