推薦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
