php中二進制子串怎么進行計數(shù)

這篇文章主要介紹php中二進制子串怎么進行計數(shù)，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

專注于為中小企業(yè)提供網(wǎng)站制作、做網(wǎng)站服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)定日免費做網(wǎng)站提供優(yōu)質(zhì)的服務。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

題目描述：

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

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

示例 1 :

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

請注意，一些重復出現(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的值就可以了，但是由于時間復雜度較高就會出現(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ù)，先記下當前的索引位置然后再求后面的數(shù)相同的個數(shù)（算法中的b）直到再次遇到與當前數(shù)不同的數(shù)或者到末尾為止，然后比較a，b的大小，count+=兩個數(shù)中的小數(shù)，那么count就是所求的答案。

以上是“php中二進制子串怎么進行計數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁題目：php中二進制子串怎么進行計數(shù)
網(wǎng)頁鏈接：http://muchs.cn/article22/jpjsjc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、自適應網(wǎng)站、標簽優(yōu)化、品牌網(wǎng)站設計、靜態(tài)網(wǎng)站、網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)