前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >推荐14-php算法题-306累加数

推荐14-php算法题-306累加数

作者头像
猿哥
发布2019-09-24 17:46:10
4150
发布2019-09-24 17:46:10
举报
文章被收录于专栏:Web技术布道师

题目描述

累加数是一个字符串,组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例

代码语言:javascript
复制
输入: "112358"
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
代码语言:javascript
复制
输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

思路

1.找出第一组前三个满足累加的数,再进行判断字符串是否为累加数。

2.如果不存在,则循环上一步操作

代码语言:javascript
复制
/**
     * @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;
        }

}
代码语言:javascript
复制
LeetCode:https://leetcode-cn.com/problems/additive-number/原文:https://segmentfault.com/a/1190000020426923
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 PHP技术大全 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 示例
  • 思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档