共计 1865 个字符,预计需要花费 5 分钟才能阅读完成。
306. 累加数
题目链接:https://leetcode-cn.com/probl…
难度:中等
题目描述
累加数是一个字符串,组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 ‘0’-‘9’ 的字符串,编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例
输入: "112358" | |
输出: true | |
解释: 累加序列为: 1, 1, 2, 3, 5, 8。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 |
输入: "199100199" | |
输出: true | |
解释: 累加序列为: 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; | |
// 回溯法,不断找出恰三个符合的累加数 | |
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; | |
} | |
// 验证整个字符串是否为累加数字符串 | |
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; | |
} | |
} |
正文完