Ссылки на Темы
696. Подсчет Двоичных Подстрок
Анализ темы
Учитывая строку 01, она возвращает количество двоичных строк, которые могут состоять только из последовательных строк 0 и 1.
Например, 00110011 Это включает в себя 0011 , 01 , 1100 , 10 , 0011 , 01 Всего шестеро. 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
Используйте идею стека. Во-первых, число помещается в стек, и когда встречаются разные числа, число освобождается из стека. Когда стек закончен, число, появляющееся после стека, принимается за следующий стек. Но об этом немного неудобно писать. Неправильный ответ написал и сдался. Поэтому я передумал.
Идея 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;
}
}Если вы считаете, что эта статья полезна для вас, вы можете воспользоваться Фондом генерации энергии Ии.