Автор оригинала: David Wong.
Ссылка на заголовок: https://leetcode-cn.com/probl…
Сложность: средняя
Название Описание
Совокупное число представляет собой строку, и его числа могут образовывать последовательность накопления.
Допустимая последовательность накопления должна содержать не менее 3 чисел. За исключением первых двух чисел, число в строке равно сумме двух предыдущих чисел.
Учитывая строку, содержащую только числа ” 0 “- 9”, напишите алгоритм, чтобы определить, является ли данный ввод аддитивным.
Примечание: число в последовательности накопления не будет начинаться с 0, поэтому не будет 1,2,03 или 1,02,3.
Примеры
Input: "112358" Output: true Explanation: the cumulative sequence is: 1, 1, 2, 3, 5, 8. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Input: "199100199" Output: true Explanation: the cumulative sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199
размышляющий
1. Определите первые три числа первой группы, которые удовлетворяют накоплению, а затем определите, является ли строка совокупным числом. 2. Если он не существует, предыдущая операция будет повторена
1
/**
* @param String $num
* @return Boolean
*/
function isAdditiveNumber($num) {
$len = strlen($num);
if($len < 3){
return false;
}
$firstNum = 0;
$secondNum = 0;
$sumNum = 0;
//The method of backtracking is used to find exactly three cumulative addends
for ($i=2; $i<$len; $i++){
$subLen = $i+1;
for($j=1;$j<(int)(($subLen+1)/2);$j++){
$firstNumLen = $j;
for($k=1;$k<(int)(($subLen+1)/2);$k++){
$secondNumLen = $k;
if(0===strpos(substr($num,0,$firstNumLen),'0') && $firstNumLen != 1){
continue;
}
if(0===strpos(substr($num,$firstNumLen,$secondNumLen),'0') && $secondNumLen!= 1){
continue;
}
if(0===strpos(substr($num,$firstNumLen+$secondNumLen,$subLen-$firstNumLen-$secondNumLen),'0') && $subLen-$firstNumLen-$secondNumLen!= 1){
continue;
}
$firstNum = (int)substr($num,0,$firstNumLen);
$secondNum = (int)substr($num,$firstNumLen,$secondNumLen);
$sumNum = (int)substr($num,$firstNumLen+$secondNumLen,$subLen-$firstNumLen-$secondNumLen);
if($firstNum+$secondNum == $sumNum){
$isAdditiveNumber = $this->verifyAdditiveNumber($num,$firstNum,$secondNum,$sumNum);
if($isAdditiveNumber){
return true;
}
}
}
}
}
return false;
}
//Verify that the entire string is an additive string
public function verifyAdditiveNumber($num,$firstNum,$secondNum,$sumNum){
if($firstNum+$secondNum != $sumNum){
return false;
}
$startIdx = 0;
while(true){
$tmpSumNum = (string)($secondNum + $sumNum);
$tmpStartLen = ($startIdx+strlen($firstNum)+strlen($secondNum)+strlen($sumNum));
if($tmpStartLen == strlen($num)){
return true;
}
if(substr($num,$tmpStartLen,strlen($tmpSumNum)) != $tmpSumNum){
return false;
}
$startIdx = $startIdx + strlen($firstNum);
$firstNum = $secondNum;
$secondNum = $sumNum;
$sumNum = (int)$tmpSumNum;
}
}Оригинал: “https://developpaper.com/php-algorithm-question-306-cumulative-number/”