PHP에서 이진 하위 문자열을 계산하는 방법

최근에 이 문제를 난이도 순으로 정리했는데, 처음에 작성한 코드가 타임아웃으로 인해 모두 실패했습니다. 다음은 이전 코드와 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 값을 반환하지만 시간 복잡도가 높기 때문에 A timeout이 발생하면 다음 알고리즘으로 변경합니다.

변경된 코드:

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와 b의 크기를 비교하고 count+= 두 숫자의 소수점을 계산하면 count가 원하는 답이 됩니다.

추천: "2021 PHP 면접 질문 요약(모음)" "php 비디오 튜토리얼"

위 내용은 PHP에서 이진 하위 문자열을 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!