Bagaimana untuk mengira substring binari dalam php

Baru-baru ini, saya datang ke soalan ini mengikut urutan kesukaran Kod yang saya tulis pada mulanya tidak lulus kerana ia tamat masa selepas melalui Baidu, saya melihat idea orang lain dan merungut bagaimana logik saya sebelum ini memakan, di bawah adalah kod saya sebelum ini dan kod selepas ac.

Perihalan masalah:

Diberi rentetan s, hitung bilangan subrentetan tidak kosong (berterusan) dengan nombor 0 dan 1 yang sama, dan semua 0 dalam subrentetan ini dan semua 1 adalah berkumpulan.

Kira bilangan kali subrentetan berulang muncul.

Contoh 1:

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

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

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

Contoh 2:

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

Kod tamat masa (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;
            }

        }

Idea sebelumnya adalah ganas Idea penyelesaian adalah untuk mencari indeks permulaan dan penamat 0 dan 1 daripada bit pertama rentetan kepada panjang rentetan Panjangnya 1, dan kemudian gunakan gelung untuk menentukan sama ada semuanya 0 atau 1 dalam. selang ini. Jika ya, kira sahaja, dan akhirnya kembalikan nilai kiraan Namun, disebabkan kerumitan masa yang tinggi, tamat masa akan berlaku, jadi tukar kepada algoritma berikut:

Kod selepas perubahan: <.>

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

Idea algoritma yang diubah suai adalah untuk merentasi dari awal hingga akhir rentetan dan mencari nombor 1s atau 0s berturut-turut (a dalam algoritma jika nombor berikut berbeza). daripada nombor sebelumnya, tuliskannya dahulu Kedudukan indeks semasa dan kemudian cari bilangan nombor berikutnya dengan nombor yang sama (b dalam algoritma) sehingga ia menemui nombor yang berbeza daripada nombor semasa sekali lagi atau mencapai penghujung, dan kemudian. membandingkan saiz a dan b, kira = dua nombor perpuluhan, kemudian kira adalah jawapan yang anda cari.

Disyorkan: "Ringkasan soalan temuduga PHP 2021 (koleksi)" "tutorial video php"

Atas ialah kandungan terperinci Bagaimana untuk mengira substring binari dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!