Leetcode PHP题解--D128 202. Happy Number


题目链接

202. Happy Number

题目分析

这道题目不复杂,就是给定一个数字,把每一位拆开来算个平方再相加。一直加到和为1就是快乐数字Happy Number返回true,或者得到循环就返回false。

解题思路

我觉得这个题目的“难点”在于怎么知道循环了。比较简单的办法是把求过的和都记录进一个数组里面,每次求完一次和就判断一下是否出现过,即可知是否循环。这种方案的缺点就是每算一次要遍历一遍数组了。

我想另辟蹊径换种方法。

我先通过分析100以内的数字种,有哪些数字是符合要求的。通过计算发现:和为100时,只可能从68或86而得来。而这两个数字又是从28或82得来的。再往前就是19和91了。而这两个数字是不可能通过100以内的数字每一位拆开求平方和得来。我们可以画出19/91=>28/82=>68/86=>100这样的链条来。
同理、还有另外两个链条:
7/70=>49/94=>79/97=>130=>10

44=>23/32=>13/31=>10

在链条里出现的数字都能保证最后得到的是1。因此我们把这些数字保存起来用来对照。一旦在计算过程中,出现了这个数字,那就说明这个数一定是快乐数字了。

最终代码

<?php
class Solution {

    /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        $safe = [1,7,10,13,19,23,28,31,28,31,32,44,49,68,70,79,82,86,91,94,97,100];
        $total = $n;
        do{
            $digits = str_split($total);
            $total = array_reduce($digits, function($val, $s){
                $val += $s*$s;
                return $val;
            }, 0);
        }while($total>100);
        if(in_array($total, $safe)){
            return true;
        }
        return false;
    }
}

若觉得本文章对你有用,欢迎用爱发电资助。


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Dcat Admin v2.0.0-BETA 版本发布,全新扩展系统上线

>> 下一篇: Leetcode PHP题解--D129 836. Rectangle Overlap