php中二进制子串怎么进行计数

这篇文章主要介绍php中二进制子串怎么进行计数，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

题目描述：

给定一个字符串 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#)：

publicclassSolution
{
publicintCountBinarySubstrings(strings)
{
stringtemp;
intcount=0;
intlength=2;
boolsign=false;
while(length<=s.Length)
{
for(inti=0;i<s.Length-length+1;i++)
{
sign=false;
temp=s.Substring(i,length);
intzeroend=temp.LastIndexOf('0');
intzerostart=temp.IndexOf('0');
intonestart=temp.IndexOf('1');
intoneend=temp.LastIndexOf('1');
if(zerostart==-1||zeroend==-1||oneend==-1||onestart==-1)
{
sign=true;
continue;
}
for(intj=zerostart+1;j<zeroend;j++)
{
if(temp[j]!='0')
{
sign=true;
break;
}
}
for(intj=onestart+1;j<oneend;j++)
{
if(temp[j]!='1')
{
sign=true;
break;
}
}
if(!sign)
count++;
}

length+=2;
}
returncount;
}

}

之前的思路是暴力求解的思路，从字符串的第一位到其Length-字串的长度+1为止，求出0，1的开始和结束索引，然后再用循环在这个区间内判断是否全部为0或1，如果是的话就count++，最后返回count的值就可以了，但是由于时间复杂度较高就会出现超时的情况，那么就更改为下面的算法:

更改后代码：

publicclassSolution
{
publicintCountBinarySubstrings(strings)
{
inta=1,b=0;
charnum;
boolsign=false;
intcount=0;
num=s[0];
inti=0;
intindex=0;
while(i<s.Length-1)
{
i++;
if(s[i]==num&&sign==false)
{
a++;
}
elseif(s[i]==num&&sign==true)
{
b++;
}
elseif(s[i]!=num&&!sign)
{
b++;
index=i;
sign=true;
num=s[i];
}
elseif(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;
}
}
returncount;
}
}

更改后算法的思路就是从字符串的开始到末尾遍历，求出连续的1或者0的个数（算法中的a），若后面的数不同于前面的数，先记下当前的索引位置然后再求后面的数相同的个数（算法中的b）直到再次遇到与当前数不同的数或者到末尾为止，然后比较a，b的大小，count+=两个数中的小数，那么count就是所求的答案。

以上是“php中二进制子串怎么进行计数”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注恰卡编程网行业资讯频道！