Comment compter les sous-chaînes binaires en php

醉折花枝作酒筹
Libérer: 2023-03-11 20:44:01
avant
1875 Les gens l'ont consulté

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)没有组合在一起。
Copier après la connexion

Exemple 2 :

输入: "10101"输出: 4解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。
Copier après la connexion

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

        }
Copier après la connexion

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;
            }
        }
Copier après la connexion

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!

Étiquettes associées:
php
source:csdn.net
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal