每天进步一点点🤏

快乐数

  • ~1.84K 字

快乐数

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
编写一个算法来判断一个数 n 是不是快乐数

「快乐数」 定义为：
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1
如果这个过程 结果为 1,那么这个数就是快乐数
如果 n 是 快乐数 就返回 true;不是,则返回 false

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
思路:
使用快慢指针的思路,快指针每次前进两次,慢指针每次前进一次
如果存在循环,快指针迟早会追上慢指针,这时候如果快(慢)指针的值不为1,返回false
如果是快乐数,则到1之后的值都只会是1,两个指针发生碰撞的值只会是1,返回true

代码:

/**
 * @param Integer $n
 *
 * @return Boolean
 */
function isHappy($n)
{
    $slow = $n;
    $fast = $n;

    // 慢指针前进一步
    $slow = $this->hp($slow);
    // 快指针前进两部
    $fast = $this->hp($fast);
    $fast = $this->hp($fast);

    if ($fast === $slow) {
        return $slow === 1;
    }

    // 如果快指针等于慢指针
    // 可能性1: 快指针循环了几圈后追上了慢指针,代表存在循环,不为1
    // 可能性2: 是快乐数,无论前进几步结果都只会是1
    while ($fast !== $slow) {
        $slow = $this->hp($slow);
        $fast = $this->hp($fast);
        $fast = $this->hp($fast);
    }

    return $slow === 1;
}

private function hp($d)
{
    $num = 0;
    while ($d > 0) {
        $l   = $d % 10;
        $num += $l * $l;
        $d   = intdiv($d, 10);
    }

    return $num;
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
思路:
将每次循环的数字存入数组,如果出现重复的,循环结束,根据重复项结果是否为1返回true或false

代码:
/**
 * @param Integer $n
 *
 * @return Boolean
 */
function isHappy($n)
{
    $arr = [];
    while (1) {
        $num = $this->hp($n);

        if (in_array($num, $arr)) {
            break;
        }
        $arr[] = $num;
        $n     = $num;
    }

    return $n === 1;
}

private function hp($d)
{
    $num = 0;
    while ($d > 0) {
        $l   = $d % 10;
        $num += $l * $l;
        $d   = intdiv($d, 10);
    }

    return $num;
}