day25【LeetCode力扣】202.快乐数

day25【LeetCode力扣】202.快乐数

1.题目描述

附上题目链接：202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1
2
3
4
5
6
7

示例 2：

输入：n = 2
输出：false
1
2

2.题解

这道题不是很难，关键在于两个步骤：1.要取各个位上的值并进行计算2.无限循环的处理

c++

class Solution {
public:
    int getSum(int n){
        int sum = 0;
        while(n){
            sum += (n%10)*(n%10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum = getSum(n);
            if(sum ==1 )
                return true;
            if(set.find(sum)!=set.end())
                return false;
            else{
                set.insert(sum);
            }
            n=sum;
        }
    }
};
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

python

使用集合1️⃣

class Solution:
    def isHappy(self, n: int) -> bool:
        record=set()
        while True:
            n=self.ger_sum(n)
            if n ==1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

    def ger_sum(self,n:int)->int:
        num = 0
        while n:
            n,r=divmod(n,10)
            num += r ** 2
        return num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

使用集合2️⃣

class Solution:
    def isHappy(self, n: int) -> bool:
        record=set()
        while n not in record:
            record.add(n)
            num = 0
            n_str=str(n)
            for i in n_str:
                num += int(i) ** 2
            if num ==1:
                return True
            else:
                n=num
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用数组

class Solution:
    def isHappy(self, n: int) -> bool:
        record=[]
        while n not in record:
            record.append(n)
            num = 0
            n_str=str(n)
            for i in n_str:
                num += int(i) ** 2
            if num ==1:
                return True
            else:
                n=num
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用快慢指针

class Solution:
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = n
        while self.get_sum(fast)!= 1 and self.get_sum(self.get_sum(fast)):
            slow = self.get_sum(slow)
            fast = self.get_sum(self.get_sum(fast))
            if slow == fast:
                return False
        return True

    def get_sum(self,n: int) -> int: 
       new_num = 0
       while n:
           n, r = divmod(n, 10)
           new_num += r ** 2
       return new_num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解释：

首先，该方法使用双指针法来判断快乐数。双指针法中，设定一个快指针 fast 和一个慢指针 slow，每次循环，让快指针走两步，慢指针走一步。如果快指针最终等于 1，则说明 n 是快乐数；如果最终快指针和慢指针相遇且不等于 1，则说明 n 不是快乐数。

在循环中，首先将快慢指针都初始化为 n。然后，使用 get_sum 方法分别计算快指针和慢指针的平方和。接着，在 while 循环中，判断快指针的平方和是否等于 1，如果是则返回 True；否则，继续执行下面的语句。在 while 循环中，每次让快指针走两步，慢指针走一步，如果最终快指针和慢指针相遇，则说明 n 不是快乐数，返回 False。

---

​ 如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

​ 如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

​ 如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！