最近刷題，按照題目的難度順序刷到了這一題，一開始寫的代碼都因為超時而沒有ac過，經(jīng)過百度后看了一下別人的思路后感嘆自己之前的邏輯是有多么的耗時，下面是我之前的代碼和ac過后的代碼。

題目描述：

給定一個字符串 s，計算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的。

重復(fù)出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。

示例 1 :

輸入: "00110011"輸出: 6解釋: 有6個子串具有相同數(shù)量的連續(xù)1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。  請注意，一些重復(fù)出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。  另外，“00110011”不是有效的子串，因為所有的0（和1）沒有組合在一起。

示例 2 :

輸入: "10101"輸出: 4解釋: 有4個子串：“10”，“01”，“10”，“01”，它們具有相同數(shù)量的連續(xù)1和0。

超時代碼(C#)：

 public class Solution         {             public int CountBinarySubstrings(string s)             {                 string temp;                 int count = 0;                 int length = 2;                 bool sign = false;                 while (length <= s.Length)                 {                     for (int i = 0; i < s.Length - length + 1; i++)                     {                         sign = false;                         temp = s.Substring(i, length);                         int zeroend = temp.LastIndexOf('0');                         int zerostart = temp.IndexOf('0');                         int onestart = temp.IndexOf('1');                         int oneend = temp.LastIndexOf('1');                         if (zerostart == -1 || zeroend == -1 || oneend == -1 || onestart == -1)                         {                             sign = true;                             continue;                         }                         for (int j = zerostart + 1; j < zeroend; j++)                         {                             if (temp[j] != '0')                             {                                 sign = true;                                 break;                             }                         }                         for (int j = onestart + 1; j < oneend; j++)                         {                             if (temp[j] != '1')                             {                                 sign = true;                                 break;                             }                         }                         if (!sign)                             count++;                     }                                        length += 2;                 }                 return count;             }          }

之前的思路是暴力求解的思路，從字符串的第一位到其Length-字串的長度+1為止，求出0，1的開始和結(jié)束索引，然后再用循環(huán)在這個區(qū)間內(nèi)判斷是否全部為0或1，如果是的話就count++，最后返回count的值就可以了，但是由于時間復(fù)雜度較高就會出現(xiàn)超時的情況，那么就更改為下面的算法:

更改后代碼：

public class Solution         {             public int CountBinarySubstrings(string s)             {                 int a = 1, b = 0;                 char num;                 bool sign = false;                 int count=0;                 num = s[0];                 int i = 0;                 int index = 0;                 while (i<s.Length-1)                 {                     i++;                     if (s[i] == num && sign == false)                     {                         a++;                     }                      else if (s[i] == num && sign == true)                     {                         b++;                     }                     else if (s[i] != num && !sign)                     {                         b++;                         index = i;                         sign = true;                         num = s[i];                     }                     else if (s[i] != num && sign)                     {                         if (a > b)                             count += b;                         else                             count += a;                         a = 1;                         b = 0;                         i = index;                         sign = false;                     }                     if(i==s.Length-1)                     {                           if (a > b)                             count += b;                         else                             count += a;                     }                 }                 return count;             }         }

更改后算法的思路就是從字符串的開始到末尾遍歷，求出連續(xù)的1或者0的個數(shù)（算法中的a），若后面的數(shù)不同于前面的數(shù)，先記下當(dāng)前的索引位置然后再求后面的數(shù)相同的個數(shù)（算法中的b）直到再次遇到與當(dāng)前數(shù)不同的數(shù)或者到末尾為止，然后比較a，b的大小，count+=兩個數(shù)中的小數(shù)，那么count就是所求的答案。

推薦：《2021年P(guān)HP面試題大匯總（收藏）》《php視頻教程》