推荐14-php算法题-306累加数
- 2019 年 10 月 7 日
- 筆記
题目描述
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 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.如果不存在，则循环上一步操作
/** * @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; } }
LeetCode：https://leetcode-cn.com/problems/additive-number/原文：https://segmentfault.com/a/1190000020426923
