So zählen Sie binäre Teilzeichenfolgen in PHP

Ich habe diese Frage kürzlich in der Reihenfolge der Schwierigkeit auf den neuesten Stand gebracht. Nachdem ich Baidu durchgesehen und mir die Ideen anderer Leute angesehen hatte, beklagte ich mich darüber, wie zeitaufwändig meine vorherige Logik war. Das Folgende ist mein vorheriger Code und der Code nach ac.

Problembeschreibung:

Zählen Sie bei einer gegebenen Zeichenfolge s die Anzahl der nicht leeren (kontinuierlichen) Teilzeichenfolgen mit der gleichen Anzahl von Nullen und Einsen, und alle Nullen und alle Einsen in diesen Teilzeichenfolgen werden miteinander kombiniert.

Wiederkehrende Teilzeichenfolgen müssen zählen, wie oft sie erscheinen.

Beispiel 1:

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

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

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

Beispiel 2:

输入: "10101"输出: 4解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

Timeout-Code (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;
            }

        }

Die vorherige Idee ist eine Brute-Force-Lösung, vom ersten Bit der Zeichenfolge bis zu ihrer Länge – der Länge der Zeichenfolge + 1 Suchen Sie die Start- und Endindizes von 0 und 1 und ermitteln Sie dann mithilfe einer Schleife, ob in diesem Intervall alle 0 oder 1 sind. Wenn ja, zählen Sie ++ und geben Sie schließlich den Wert von count zurück, jedoch aufgrund der hohen Zeitkomplexität A Tritt eine Zeitüberschreitung auf, wechseln Sie dann zum folgenden Algorithmus:

Der geänderte Code:

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

Die Idee des geänderten Algorithmus besteht darin, vom Anfang bis zum Ende der Zeichenfolge zu durchlaufen, um die Anzahl der aufeinanderfolgenden Einsen oder Nullen zu ermitteln ( A) Wenn sich im Algorithmus die folgende Zahl von der vorherigen Zahl unterscheidet, zeichnen Sie zuerst die aktuelle Indexposition auf und suchen Sie dann die gleiche Zahl wie die folgende Zahl (b im Algorithmus), bis Sie erneut auf eine Zahl stoßen, die sich von der aktuellen Zahl unterscheidet oder Gehen Sie zum Ende und vergleichen Sie dann die Größen von a und b, count+= die Dezimalzahl der beiden Zahlen, dann ist count die gesuchte Antwort.

Empfohlen: "Zusammenfassung der PHP-Interviewfragen 2021 (Sammlung)" "php-Video-Tutorial"

Das obige ist der detaillierte Inhalt vonSo zählen Sie binäre Teilzeichenfolgen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!