文档章节

Leetcode PHP题解--D88 696. Count Binary Substrings

skys215
 skys215
发布于 06/17 05:29
字数 763
阅读 8
收藏 0
PHP

D88 696. Count Binary Substrings

题目链接

696. Count Binary Substrings

题目分析

给定一个01字符串,返回仅用连续的0和1串所能组成的二进制字符串个数。

例如,00110011,就包含001101110010001101共6个。001100则不算,因为两个00被11分割开了,不是连续的。

思路

思路1:

生成01,0011,000111和10,1100,111000字符串,再用substr_count函数去计算个数的。但是会超时。

function countBinarySubstrings($s) {
    $totalLength = strlen($s);
    $total = 0;
    for($i=0;$i<=$totalLength/2; $i++){
        //01 0011 000111
        $boz = str_repeat('0',$i).str_repeat('1',$i);
        //10 1100 111000
        $bzo = strrev($boz);
        $total += substr_count($s, $boz);
        $total += substr_count($s, $bzo);
    }
    return $total;
}

思路2

用栈的思想。先把数字压入栈内,遇到不同数字时出栈。出完栈时,把后面出现的数字顶上,作为下一个出栈的栈。然而写起来略嫌麻烦。写了个Wrong Answer出来就放弃了。于是又换了个思路。

思路3

只记录前一组是0还是1,以及出现的次数。

先取字符串的第一个字符作为第一组的字符。
从第二个字符开始判断。
判断是否与第一组出现的字符相同。相同,则判断是否与前一个字符相同。这里需要注意的是,前一组的字符不一定等于前一个字符。所以需要分开判断。
如果与前一个字符相同,则给前一组字符出现个数(或者叫长度)+1。如果与前一个字符不同,则说明两个相同的字符夹住了不同的字符(例如010或者101)。那么此时需要抛弃前一组的所有内容。因为前一组已经没有内容可以和下一组匹配了。所以需要把当前组作为前一组,把当前字符作为下一组。

如果当前字符与前一组的字符不同,则说明配对成功。
前一组未配对字符数量减1,当前组未配对数量+1。这里是因为,当前在变成前一组的时候,会与其后面的字符匹配,到时候会减去对应数量。因此这里需要+1。

当前一组未配对字符数量达到0时,说明前一组已经没有可以匹配的字符。故把当前组替换未前一组。

如此循环即可。

最终代码

<?php
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function countBinarySubstrings($s) {
        $total = 0;
        $s = str_split($s);
        $stack1 = array_shift($s);
        $stack1Amount = 1;
        $stack2 = null;
        $stack2Amount = 0;
        $prev = $stack1;
        foreach($s as $key => $val){
            if($stack1 == $val){
                if($val == $prev){
                    $stack1Amount++;
                }
                else{
                    $stack1 = $stack2;
                    $stack1Amount = $stack2Amount;
                    $stack2Amount = 0;
                    $stack2 = null;
                }
            }
            if($stack1 != $val){
                $stack2 = $val;
                $stack2Amount++;
                $stack1Amount--;
                $total++;
            }
            if($stack1Amount == 0){
                $stack1 = $stack2;
                $stack1Amount = $stack2Amount;
                $stack2 = null;
                $stack2Amount = 0;
            }
            $prev = $val;
        }
        return $total;
    }
}

若觉得本文章对你有用,欢迎用爱发电资助。

© 著作权归作者所有

skys215
粉丝 9
博文 105
码字总数 31388
作品 0
深圳
后端工程师
私信 提问
696. Count Binary Substrings - LeetCode

Question 696. Count Binary Substrings Example 1: Example 2: Solution 思路:题目大意是,给一个二进制的字符串,问有多少子串的0个数量等于1的数量且子串中0和1不能交替出现。 Java实现:...

yysue
2018/06/29
0
0
LeetCode 攻略 - 2019 年 7 月上半月汇总

Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 14:13:38 一 目录 不折腾的前端,和咸鱼有什么区别 目录 一 目录 二 前言 三 汇总  3.1 LeetCode 已攻略  3.2...

jsliang
前天
0
0
LeetCode 攻略 - 2019 年 6 月汇总

Create by jsliang on 2019-06-28 09:03:23 Recently revised in 2019-06-28 14:56:36 一 目录 不折腾的前端,和咸鱼有什么区别 目录 一 目录 二 前言 三 汇总  3.1 已攻略  3.2 Function ...

jsliang
06/28
0
0
LeetCode 401 Binary Watch

LeetCode 排列组合 题目汇总 LeetCode 数字 题目汇总 LeetCode 动态规划 题目分类汇总 干货!LeetCode 题解汇总 题目描述 A binary watch has 4 LEDs on the top which represent the hours...

被称为L的男人
2017/12/10
0
0
【Leetcode】647. Palindromic Substrings

Description Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as diffe......

xiagnming
2018/07/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux的基本命令

目录的操作命令(增删改查) 增: mkdir 目录名称; 查: ls 可以看到该目录下的所有的目录和文件 ls -a,可以看到该目录下的所有文件和目录,包括隐藏的 ls -l,可以看到该目录下的所有目录和...

凹凸凸
今天
2
0
在古老unix中增加新用户

Installing 4.3 BSD Quasijarus on SIMH 目标:要在4.3BSD中新增加用户dmr,指定目录/home/dmr,uid为10 gid=31(guest组,系统已建立) 4.3BSD还没有adduser或useradd 直接修改/etc/passwd...

wangxuwei
今天
2
0
Bootstrap(六)表单样式

基本样式 所有设置了 .form-control 类的 <input>、<textarea> 和 <select> 元素都将被默认设置宽度属性为 width: 100%;。 将 label 元素和前面提到的控件包裹在 .form-group 中可以获得最好...

ZeroBit
昨天
3
0
SSL 证书格式转换

SSL 证书格式转换 不同服务器情况下,需要不同的证书格式。 比如 pem 转 pfx。 pem在window 平台下可以导入,但是无法正常使用。 需要转换成pfx。 推荐在线转换工具,由中国数字证书网站提供...

DrChenXX
昨天
2
0
HAProxy

xx

Canaan_
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部