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

Leetcode · curry · 于 2个月前 发布 · 152 次阅读

题目描述

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

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 0 条回复 php 算法
没有找到数据。
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂