運行（C＃）算法評估

我最近在做編程算法，只是爲了練習:)。我從一個網站得到了這個問題。問題是：運行（C＃）算法評估

編寫一個函數，用於查找字符串中最長運行的從零開始的索引。跑步是相同字符的連續序列。如果有多個具有相同長度的運行，則返回第一個的索引。

例如，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); 
    }

這是過去我對測試的主要目的。但是它在性能基準測試中失敗了。任何人都可以闡明我的代碼如何優化？謝謝。

來源

2015-10-27 under_score

什麼問題？您正在遍歷字符串一次，這在任何情況下都是必需的。 – vish4071

問題是測試用例似乎有我的代碼更好的版本，要精簡更優化。 –

我不知道你是否需要檢查每一個下一個字符，一旦你已經發現了一個長度爲N的運行。既然如果字符[i]和[i + N]不同，那麼很明顯，沒有更大的運行這兩個字符之間的長度。 – user4637357

您可以在幾個方面進行優化：

首先，occurenceCounter > counter條件if是多餘的。
此外，請勿使用str.IndexOf()。相反，只要其occurrenceCounter變得大於maxOccur，就嘗試將索引存儲在變量中。這應該很容易。（提示：你知道當前的索引和計數）

除此之外，我看不到代碼是否可以優化。另外，我對C＃不太熟悉，所以，我不知道你是否有一個char類型（肯定是）。如果您必須比較單個字符，建議不要使用strings進行比較。（類似toChar應該比toString快）。

此外，我不認爲你的代碼將通過所有的測試用例。檢查：kaaabbb。你的代碼會返回4（我認爲）（正確的o/p是1）。

爲此，循環直到string.length - 2（不是string.length - 1，如同您所做的那樣），並且在分配val2時刪除if條件。

來源

2015-10-27 07:25:31 vish4071

爲什麼使用轉換.ToString？這需要時間。我懷疑C＃具有char類型的字符串元素。你最好使用索引，而不是使用運行字符串。僞碼：

MaxLen = 0 
MaxIndex = 0 
StartIndex = 0 
StartChar = s[0] 
for i = 1 to s.Length - 1 do 
    if s[i] != StartChar then 
     Len = i - StartIndex 
     if MaxLen < Len then 
      MaxLen = Len 
      MaxIndex = StartIndex 
     StartIndex = i 
     StartChar = s[i] 
Len = s.Length - StartIndex 
    if MaxLen < Len then 
      MaxLen = Len 
      MaxIndex = StartIndex

來源

2015-10-27 07:42:09 MBo

運行（C＃）算法評估

回答

相關問題