189 8069 5689

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#):

 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('0');
                        int zerostart = temp.IndexOf('0');
                        int onestart = temp.IndexOf('1');
                        int oneend = temp.LastIndexOf('1');
                        if (zerostart == -1 || zeroend == -1 || oneend == -1 || onestart == -1)
                        {
                            sign = true;
                            continue;
                        }
                        for (int j = zerostart + 1; j < zeroend; j++)
                        {
                            if (temp[j] != '0')
                            {
                                sign = true;
                                break;
                            }
                        }
                        for (int j = onestart + 1; j < oneend; j++)
                        {
                            if (temp[j] != '1')
                            {
                                sign = true;
                                break;
                            }
                        }
                        if (!sign)
                            count++;
                    }
                  
                    length += 2;
                }
                return count;
            }

        }

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

更改后代码:

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 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就是所求的答案。

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


新闻名称:php中二进制子串怎么进行计数
浏览路径:http://cdxtjz.cn/article/jpjsjc.html

其他资讯