算法来判断一个数 n 是不是快乐数。"/>
编写一个算法来判断一个数 n 是不是快乐数。
题意:
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
示例 1:
输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2:
输入:n = 2
输出:false
提示:
1 <= n <= 2^31 - 1
解题方法:
解法一:
思路
这道题目看上去貌似一道数学问题,其实并不是!
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!
正如:关于哈希表,你该了解这些!中所说,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。
所以这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
还有一个难点就是求和的过程,如果对取数值各个位上的单数操作不熟悉的话,做这道题也会比较艰难。
代码:
class Solution {/*** @param Integer $n* @return Boolean*/function isHappy($n) {$table = [];while ($n != 1 && !isset($table[$n])) {$table[$n] = 1;$n = self::getNextN($n);}return $n == 1;}function getNextN(int $n) {$res = 0;while ($n > 0) {$temp = $n % 10;$res += $temp * $temp;$n = floor($n / 10);}return $res;}
}
参考:
作者:代码随想录
链接:/
自己想的方法(错误的方法,与其他方法做一个对比):会出现运行时间过长的问题
function isHappy($n) {if($n == 1){return true;}$str = strval($n);$res = 0;$hash = [];for($i = 0; $i < strlen($str); $i++){$res = intval($str[$i]) * intval($str[$i]);}if(isset($hash[$res])){return false;} else {$hash[$res] = 1;}if($res == 1){return true;}else{return $this->isHappy($res);}}
方法二: 反其道行之
思路
相当的一个笨办法 经过测试发现不快乐的数字最后都会变成4
那么只需要判断这个数值是1
则返回true
是4
则返回false
class Solution {/*** @param Integer $n* @return Boolean*/function isHappy($n) {if ($n == 1){return true;} else if ($n == 4){return false;} else{$n_arr = str_split((string)$n);// print_r($n_arr);exit;$new_n = 0;foreach($n_arr as $num){$new_n += pow($num,2);// print_r($new_n);exit;}// echo $new_n;die;return $this->isHappy($new_n);}}
}
参考:
作者:踌躇
链接:/
更多推荐
编写一个算法来判断一个数 n 是不是快乐数。
发布评论