Leetcode之PHP版题目解析（202. Happy Number）

2019-3-15 星期五  开始吧

题目描述

这道题的名字真好听,开心数字.他的定义是:从任何数字开始,把当前数字替换为它的平方和.并重复着这个过程,直到数字等于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;
       
    }

优化

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

这里我们可以得出一个结论只要是循环数字,必定包含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;
       
    }

周末愉快