PHPでバイナリ部分文字列を数える方法

最近、この質問を難易度順にブラッシュアップしました。最初に書いたコードはすべてタイムアウトで失敗しました。Baidu を経由して他の人のアイデアを見て、以前のロジックはどうだったのかと嘆きました。時間がかかりました。 、以下は以前のコードと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;
            }

        }

前のアイデアは、文字列の最初のビットからその長さ (文字列の長さ) 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 と a の大きさを比較します。 b、count = 2 つの数値の小数点、つまり count が探しているものです。 答え。

おすすめ: 《2021年PHP面接質問まとめ（集）》《phpビデオチュートリアル》

以上がPHPでバイナリ部分文字列を数える方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。