Comment compter les sous-chaînes binaires en php

J'ai récemment revu cette question par ordre de difficulté. Les codes que j'ai écrits au début ont tous échoué à cause de délais d'attente. Après avoir parcouru Baidu et examiné les idées des autres, j'ai déploré le temps que prenait ma logique précédente. ce qui suit est mon code précédent et le code après ac.

Description du problème :

Étant donné une chaîne s, comptez le nombre de sous-chaînes non vides (continues) avec le même nombre de 0 et de 1, et tous les 0 et tous les 1 de ces sous-chaînes sont combinés.

Les sous-chaînes récurrentes doivent compter le nombre de fois où elles apparaissent.

Exemple 1 :

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

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

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

Exemple 2 :

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

Code de délai d'attente (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;
            }

        }

L'idée précédente est une solution par force brute, du premier bit de la chaîne à sa longueur - la longueur de la chaîne + 1 , recherchez les index de début et de fin de 0 et 1, puis utilisez une boucle pour déterminer si tous valent 0 ou 1 dans cet intervalle. Si c'est le cas, count++, et retournez enfin la valeur de count, mais en raison de la complexité temporelle élevée A. un délai d'attente se produira, puis passez à l'algorithme suivant :

Le code modifié :

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

L'idée de l'algorithme modifié est de parcourir du début à la fin de la chaîne pour trouver le nombre de 1 ou de 0 consécutifs ( A) dans l'algorithme, si le numéro suivant est différent du numéro précédent, enregistrez d'abord la position actuelle de l'index, puis recherchez le numéro des mêmes numéros suivants (b dans l'algorithme) jusqu'à ce qu'il rencontre à nouveau un numéro différent du numéro actuel ou Allez jusqu'à la fin, puis comparez les tailles de a et b, count+= la décimale des deux nombres, alors count est la réponse que vous recherchez.

Recommandé : "Résumé des questions d'entretien PHP 2021 (collection)" "Tutoriel vidéo PHP"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!