摘要:则不算,因为两个被分割开了,不是连续的。思路只记录前一组是还是,以及出现的次数。相同,则判断是否与前一个字符相同。那么此时需要抛弃前一组的所有内容。当前一组未配对字符数量达到时,说明前一组已经没有可以匹配的字符。故把当前组替换未前一组。
D88 696. Count Binary Substrings 题目链接
696. Count Binary Substrings
题目分析给定一个01字符串,返回仅用连续的0和1串所能组成的二进制字符串个数。
例如,00110011,就包含0011,01,1100,10,0011,01共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时,说明前一组已经没有可以匹配的字符。故把当前组替换未前一组。
如此循环即可。
最终代码$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; } }
若觉得本文章对你有用,欢迎用爱发电资助。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/31731.html
Problem Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively. Subs...
摘要:题目链接题目分析在二叉树中,若两个叶子节点的层数相同,但具有不同的父节点,那么这两个节点互为节点。给定一个二叉树及两个节点,返回两个节点在二叉树中,是否互为节点。遍历完成后,直接判断数组中对应的值是否相同即可。 D76 993. Cousins in Binary Tree 题目链接 993. Cousins in Binary Tree 题目分析 在二叉树中,若两个叶子节点的层数相同...
摘要:题目链接题目分析给定一个数字,返回其二进制形式中,和是否交替出现。若为偶数,最低位为,那么只能重复出现串。根据以上规则创建长度为给定数字二进制长度一半的串,并转换为十进制。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D58 693. Binary Number with Alternating Bits 题目链接 693. Binary Number with Alternati...
摘要:题目链接题目分析反转二叉树。思路类似反转两个变量,先把左右子树存进单独的变量,再相互覆盖左右子树。并对子树进行相同的操作。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D59 226. Invert Binary Tree 题目链接 226. Invert Binary Tree 题目分析 反转二叉树。 思路 类似反转两个变量,先把左右子树存进单独的变量,再相互覆盖左右子树。 并...
摘要:题目链接题目分析给定一个数字,计算其二进制表示中,出现的两个最大距离。因为只有一个是没办法比较距离的。当出现时,判断当前距离是否大于记录的最大值。最后判断当只有一个时,直接返回。否则返回所记录的最大距离。 D47 868. Binary Gap 题目链接 868. Binary Gap 题目分析 给定一个数字,计算其二进制表示中,出现的两个1最大距离。 思路 当然是先转换成二进制了。再...
阅读 2953·2021-11-22 12:06
阅读 574·2021-09-03 10:29
阅读 6442·2021-09-02 09:52
阅读 1995·2019-08-30 15:52
阅读 3379·2019-08-29 16:39
阅读 1165·2019-08-29 15:35
阅读 2042·2019-08-29 15:17
阅读 1368·2019-08-29 11:17