算法题-＞快乐数的C语言和JAVA版本的双指针解法_快乐数 java 快慢指针

快乐数的C语言和JAVA版本的双指针解法

题目描述

力扣链接:https://leetcode.cn/problems/happy-number/description/

题意:循环获取一个数平方和,如果不为1,把该数平方和的值继续循环获取平方和,如果是始终得不到1,则为false,得到1,为true.

主要问题:如何判断该值是否能得到1,那么就知道一个前提,使用快慢指针(一个走一步,一个走两步)无论如何是一定会返回到循环中的一个值.

图解释一定相遇问题:

快乐数图

不快乐情况图

由图观察可以发现无论是否为快乐数必然会相遇,那么如何判断是否为快乐数?判断相遇值是否为1,为1就是快乐数,不为1,则不是快乐数.

解题步骤:

1.定义快慢指针

2.找到每个数平方和

3.循环判断是否相等

4.循环结束,判断结束结果是否为1.

C语言代码如下:

//求和,因为需要多次使用求和,直接封装成一个函数
int bitSum(int n) {
    int sum = 0;
    while(n) {
        int tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}
bool isHappy(int n) {
    //快慢双指针
    //1.定义slow,fast
    int slow = n;
    int fast = bitSum(n);//需要先进行一次求和
    //2.找到交点
    //3.判断是否相等
    while(slow != fast) {
        slow = bitSum(slow);//对原来基础上的数进行新的求和
        fast = bitSum(bitSum(fast));//需要多走一步,嵌套求和
    }
    return slow == 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

JAVA代码如下:

class Solution {
    public int bitSum(int n) {
        int sum = 0;
        while(n != 0) {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int fast = bitSum(n);
        int slow = n;
        while(fast != slow) {
            fast = bitSum(bitSum(fast));
            slow = bitSum(slow);
        }
        return slow == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21