php中二進位子字串如何進行計數

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

題目描述：

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

重複出現的子字串要計算它們出現的次數。

範例1 :

输入: "00110011"输出: 6解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

範例2 :

输入: "10101"输出: 4解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续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(&#39;0&#39;);
                        int zerostart = temp.IndexOf(&#39;0&#39;);
                        int onestart = temp.IndexOf(&#39;1&#39;);
                        int oneend = temp.LastIndexOf(&#39;1&#39;);
                        if (zerostart == -1 || zeroend == -1 || oneend == -1 || onestart == -1)
                        {
                            sign = true;
                            continue;
                        }
                        for (int j = zerostart + 1; j < zeroend; j++)
                        {
                            if (temp[j] != &#39;0&#39;)
                            {
                                sign = true;
                                break;
                            }
                        }
                        for (int j = onestart + 1; j < oneend; j++)
                        {
                            if (temp[j] != &#39;1&#39;)
                            {
                                sign = true;
                                break;
                            }
                        }
                        if (!sign)
                            count++;
                    }
                  
                    length += 2;
                }
                return count;
            }

        }

之前的思路是暴力求解的思路，從字符串的第一位到其Length-字符串的長度1為止，求出0，1的開始和結束索引，然後再用循環在這個區間內判斷是否全部為0或1，如果是的話就count ，最後傳回count的值就可以了，但是由於時間複雜度較高就會出現超時的情況，那麼就更改為下面的演算法:

更改後程式碼：

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

更改後演算法的想法就是從字串的開始到末尾遍歷，求出連續的1或者0的個數（演算法中的a），若後面的數不同於前面的數，先記下當前的索引位置然後再求後面的數相同的個數（演算法中的b）直到再次遇到與當前數不同的數或到末尾為止，然後比較a，b的大小，count =兩個數中的小數，那麼count就是所求的答案。

推薦：《2021年PHP面試題大匯總（收藏）》《php影片教學》

以上是php中二進位子字串如何進行計數的詳細內容。更多資訊請關注PHP中文網其他相關文章！