Leetcode之PHP版题目解析(202. Happy Number)

2019-3-15 期五  

37144860a01c195bb8d3213fa836a1cc.png


题目描述

这道题的名字真好听,开心数字.他的定义是:从任何数字开始,把当前数字替换为它的平方和.并重复着这个过程,直到数字等于1,或者无限循环并且不等于1,如果最后是1结尾的话,那么他就是一个开心数字.


题目分析

我这里的想法是,用一个数组来存储出现过的数,每次生成一个新的数组,那么就判断这个数存不存在这个数组,如果存在,说明已经循环过一次了,那么直接退出,然后进行比较他等不等于1,如果等于就返回true,否则返回false


具体实现

  /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        $data=[];
        while($n !==1){
            $res=0;
            while($n){
                $res +=($n%10)*($n%10);
                $n /=10;
            }
            if(in_array($res,$data)) {
                break;
            }
            array_push($data,$res);
            $n=$res;
        }
        return $n==1;
       
    }


优化

我这里用了数组来存储出现的数,完全是在浪费存储空间,在优化之前,我们来看一组无限循环的例子.

722bf553b674593aa4230d0c7b350875.png

这里我们可以得出一个结论只要是循环数字,必定包含4,可以反着来推,$n等于4的时候,那么只能是2²=4,继续,现在$n=2,那么必定是1²+1².....

我这里并不需要额外的存储空间来存储数据.


优化代码

     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
    
         while($n !==1 && $n !==4) {
            $res=0;
            while($n){
                $res +=($n%10)*($n%10);
                $n /=10;
            }
            $n=$res;
        }
        return $n==1;
       
    }

周末愉快


吴亲库里 has written 86 articles

情绪只是对自己无能的愤怒

积分:4182 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?