<p align="center">
<a href="https://programmercarl.com/other/kstar.html" target="_blank">
  <img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210924105952.png" width="1000"/>
</a>
<p align="center"><strong><a href="https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！</strong></p>



> 该用set的时候，还是得用set

# 第202题. 快乐数

[力扣题目链接](https://leetcode-cn.com/problems/happy-number/)

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

**示例：**

输入：19     
输出：true    
解释：           
1^2 + 9^2 = 82        
8^2 + 2^2 = 68     
6^2 + 8^2 = 100   
1^2 + 0^2 + 0^2 = 1    

# 思路

这道题目看上去貌似一道数学问题，其实并不是！

题目中说了会 **无限循环**，那么也就是说**求和的过程中，sum会重复出现，这对解题很重要！**

正如：[关于哈希表，你该了解这些！](https://programmercarl.com/哈希表理论基础.html)中所说，**当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。**

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

**还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。**

C++代码如下：

```CPP
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;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};
```




# 其他语言版本


Java：
```java
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}
```

Python：
```python
class Solution:
    def isHappy(self, n: int) -> bool:
        def calculate_happy(num):
            sum_ = 0
            
            # 从个位开始依次取，平方求和
            while num:
                sum_ += (num % 10) ** 2
                num = num // 10
            return sum_

        # 记录中间结果
        record = set()

        while True:
            n = calculate_happy(n)
            if n == 1:
                return True
            
            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
            if n in record:
                return False
            else:
                record.add(n)

```

Go：
```go
func isHappy(n int) bool {
    m := make(map[int]bool)
    for n != 1 && !m[n] {
        n, m[n] = getSum(n), true
    }
    return n == 1
}

func getSum(n int) int {
    sum := 0
    for n > 0 {
        sum += (n % 10) * (n % 10)
        n = n / 10
    }
    return sum
}
```

javaScript:

```js
var isHappy = function (n) {
    let m = new Map()

    const getSum = (num) => {
        let sum = 0
        while (n) {
            sum += (n % 10) ** 2
            n = Math.floor(n / 10)
        }
        return sum
    }

    while (true) {
        // n出现过，证明已陷入无限循环
        if (m.has(n)) return false
        if (n === 1) return true
        m.set(n, 1)
        n = getSum(n)
    }
}

// 方法二：使用环形链表的思想 说明出现闭环 退出循环
var isHappy = function(n) {
    if (getN(n) == 1) return true;
    let a = getN(n), b = getN(getN(n));
    // 如果 a === b 
    while (b !== 1 && getN(b) !== 1 && a !== b) {
        a = getN(a);
        b = getN(getN(b));
    }
    return b === 1 || getN(b) === 1 ;
};

// 方法三：使用Set()更简洁
/**
 * @param {number} n
 * @return {boolean}
 */

var getSum = function (n) {
    let sum = 0;
    while (n) {
        sum += (n % 10) ** 2;
        n =  Math.floor(n/10);
    }
    return sum;
}
var isHappy = function(n) {
    let set = new Set();   // Set() 里的数是惟一的
    // 如果在循环中某个值重复出现，说明此时陷入死循环，也就说明这个值不是快乐数
    while (n !== 1 && !set.has(n)) {
        set.add(n);
        n = getSum(n);
    }
    return n === 1;
};

// 方法四：使用Set()，求和用reduce
var isHappy = function(n) {
    let set = new Set();
    let totalCount;
    while(totalCount !== 1) {
        let arr = (''+(totalCount || n)).split('');
        totalCount = arr.reduce((total, num) => {
            return total + num * num
        }, 0)
        if (set.has(totalCount)) {
            return false;
        }
        set.add(totalCount);
    }
    return true;
};
```

TypeScript:

```typescript
function isHappy(n: number): boolean {
    // Utils
    // 计算val各位的平方和
    function calcSum(val: number): number {
        return String(val).split("").reduce((pre, cur) => (pre + Number(cur) * Number(cur)), 0);
    }

    let storeSet: Set<number> = new Set();
    while (n !== 1 && !storeSet.has(n)) {
        storeSet.add(n);
        n = calcSum(n);
    }
    return n === 1;
};
```

Swift：

```swift
// number 每个位置上的数字的平方和
func getSum(_ number: Int) -> Int {
    var sum = 0
    var num = number
    while num > 0 {
        let temp = num % 10
        sum += (temp * temp)
        num /= 10
    }
    return sum
}
func isHappy(_ n: Int) -> Bool {
    var set = Set<Int>()
    var num = n
    while true {
        let sum = self.getSum(num)
        if sum == 1 {
            return true
        }
        // 如果这个sum曾经出现过，说明已经陷入了无限循环了
        if set.contains(sum) {
            return false
        } else {
            set.insert(sum)
        }
        num = sum
    }
}
```

PHP:
```php
class Solution {
    /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        // use a set to record sum
        // whenever there is a duplicated, stop
        // == 1 return true, else false
        $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;
    }
}
```

C:
```C
typedef struct HashNodeTag {
    int key;   /* num  */
    struct HashNodeTag *next;
}HashNode;

/* Calcualte the hash key */
static inline int hash(int key, int size) {
    int index = key % size;
    return (index > 0) ? (index) : (-index);
}

/* Calculate the sum of the squares of its digits*/
static inline int calcSquareSum(int num) {
    unsigned int sum = 0;
    while(num > 0) {
        sum += (num % 10) * (num % 10);
        num = num/10; 
    }
    return sum;
}

#define HASH_TABLE_SIZE     (32)

bool isHappy(int n){
    int sum = n;
    int index = 0;
    bool bHappy = false;
    bool bExit = false;
    /* allocate the memory for hash table with chaining method*/
    HashNode ** hashTable = (HashNode **)calloc(HASH_TABLE_SIZE, sizeof(HashNode));
    
    while(bExit == false) {
        /* check if n has been calculated */
        index = hash(n, HASH_TABLE_SIZE);

        HashNode ** p = hashTable + index;

        while((*p) && (bExit == false)) {
            /* Check if this num was calculated, if yes, this will be endless loop */
            if((*p)->key == n) { 
                bHappy = false;
                bExit = true;
            }
            /* move to next node of the same index */
            p = &((*p)->next);
        }

        /* put n intot hash table */
        HashNode * newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode->key = n;
        newNode->next = NULL;

        *p = newNode;

        sum = calcSquareSum(n);
        if(sum == 1) {
            bHappy = true;
            bExit = true;
        }
        else {
            n = sum;
            
        }
    }

    return bHappy;
}
```
-----------------------
<div align="center"><img src=https://code-thinking.cdn.bcebos.com/pics/01二维码一.jpg width=500> </img></div>
