php algorithm questions: 306 cumulative number

306. Cumulative Number

Topic link: https://leetcode-cn.com/probl...

Difficulty: Medium

Title Description

The accumulative number is a string, and the numbers that make up it can form an accumulative sequence.

A valid cumulative sequence must contain at least three numbers. Except for the first two numbers, the other numbers in the string are equal to the sum of the previous two numbers.

Given a string containing only the number'0'-'9', write an algorithm to determine whether a given input is an accumulative number.

Explanation: Numbers in the cumulative sequence do not start with 0, so there will be no cases of 1, 2, 03 or 1, 02, 3.

Example

Input: "112358"
Output: true 
Interpretation: 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 
Interpretation: The cumulative sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199

thinking

1. Find out the first three numbers satisfying the accumulation in the first group, and then judge whether the string is the accumulation number.
2. If it does not exist, loop the previous step

1

/**
     * @param String $num
     * @return Boolean
     */
    function isAdditiveNumber($num) {
        $len = strlen($num);
        if($len < 3){
            return false;
        }
        $firstNum = 0;
        $secondNum = 0;
        $sumNum = 0;

        //Backtracking method, constantly find exactly three coincident accumulative numbers
        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 accumulative numeric 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;
        }
    }

Tags: PHP

Posted on Mon, 07 Oct 2019 13:51:09 -0700 by Magicman0022