algorithm - 运行(C#)算法评估

Question

我最近一直在做编程算法，只是为了练习:)。我从一个网站得到了这个问题。问题是:

Write a function that finds the zero-based index of the longest run in a string. A run is a consecutive sequence of the same character. If there is more than one run with the same length, return the index of the first one.

例如，IndexOfLongestRun("abbcccddddcccbba") 应该返回 6，因为最长的运行是 dddd，它首先出现在索引 6 上。

所以我想到的是:

public static int IndexOfLongestRun(string str)
    {
        string retval = string.Empty;
        string firstOccurence = string.Empty;
        string maxOccurence = string.Empty;
        string val1 = string.Empty;
        string val2 = string.Empty;
        int counter = 1;
        int occurenceCounter = 1;
        int maxOccur = 0;

        for (int i = 0; i < str.Length; i++)
        {
            val1 = str[i].ToString();
            if (i < str.Length - 1)
            {
                val2 = str[i + 1].ToString();
            }
            else
            {
                val2 = str[i].ToString();
            }

            if (val1 == val2)
            {
                firstOccurence = val1;
                occurenceCounter = occurenceCounter + counter;

                if (occurenceCounter > counter && occurenceCounter > maxOccur)
                {
                    maxOccur = occurenceCounter;
                    maxOccurence = firstOccurence;
                }
                continue;
            }
            else
            {
                occurenceCounter = 1;
            }
        }
        return str.IndexOf(maxOccurence, 0);
    }

这超出了我测试的主要目的。但是它在性能基准上让我失望。谁能阐明如何优化我的这段代码？谢谢。

Answer 1

您可以通过几种方式对其进行优化:

• 首先，if 中的occurenceCounter > counter 条件是多余的。
• 另外，不要使用 str.IndexOf()。相反，一旦 occurrenceCounter 大于 maxOccur，就尝试将索引存储在变量中。那应该很容易。 (提示:你知道当前索引和计数)

除此之外，我看不出代码是否可以优化。另外，我不太熟悉 C#，所以，我不知道你那里是否有 char 类型(肯定是)。如果你必须比较单个字符，我建议不要使用 strings 来比较。 (类似 toChar 的东西应该比 toString 更快)。

另外，我认为您的代码不会通过所有测试用例。检查:kaaabbb。您的代码将返回 4(我认为)(正确的 o/p 是 1)。

为此，循环直到 string.length - 2(不是 string.length - 1，就像你正在做的那样)并删除 if val2 的赋值条件。