刷题笔记:力扣第202题-快乐数

1.本题刚开始没有思路，后来发现题目中说如果不是快乐数，那么就会陷入循环，本质上还是在考察哈希表。完整代码如下：

1. typedef struct{ 2. int key; 3. UT_hash_handle hh; 4. } HashEntry; 5. 6. // 计算数字每位平方和 7. int getSum(int num){ 8. int sum = 0; 9. // 拆分每一位数字 10. while (num){ 11. // 取出个位 12. int tmp = num % 10; 13. // 累加平方值 14. sum += tmp * tmp; 15. // 去掉个位 16. num /= 10; 17. } 18. 19. return sum; 20. } 21. 22. bool isHappy(int n) { 23. // 初始化空哈希表，存储出现过的平方和 24. HashEntry* hashTable = NULL; 25. while (1){ 26. // 更新n为各位平方和 27. n = getSum(n); 28. // 平方和等于1，是快乐数，直接返回true 29. if (n == 1) return true; 30. 31. HashEntry* entry; 32. // 在哈希表查找当前平方和 33. HASH_FIND_INT(hashTable, &n, entry); 34. if (entry == NULL){ 35. // 未出现过，新建哈希节点存入哈希表 36. entry = (HashEntry*)malloc(sizeof(HashEntry)); 37. entry->key = n; 38. HASH_ADD_INT(hashTable, key, entry); 39. } else { 40. // 当前值重复出现，进入循环，不是快乐数 41. return false; 42. } 43. } 44. 45. return false; 46. }

该算法时间复杂度和空间复杂度均为O(logn)（求每位数平方和所需要的时间为logn）。

2.本题的另一种解法是快慢双指针，即弗洛伊德判圈算法，类似于力扣第142题-环形链表Ⅱ。快指针每次计算两次（即计算两次每位数的平方和），慢指针每次计算一次。如果是快乐数，那么快指针会先到达1；如果不是快乐数，则快慢指针会进入循环，因为快指针只相对于慢指针多计算了一次，所以快慢指针最终一定会相遇。完整代码如下：

1. // 计算一个数字每一位的平方和 2. int getSum(int num){ 3. int sum = 0; 4. // 循环拆分数字每一位 5. while (num){ 6. // 取出个位数字 7. int tmp = num % 10; 8. // 累加当前位平方 9. sum += tmp * tmp; 10. // 去掉个位，数字缩小十倍 11. num /= 10; 12. } 13. 14. return sum; 15. } 16. 17. bool isHappy(int n) { 18. // 快慢指针初始化：slow走1次平方和，fast直接走2次平方和 19. int fast = getSum(getSum(n)), slow = getSum(n); 20. // 快指针不等于1说明还未找到快乐数终点 21. while (fast != 1){ 22. // 快指针一次两步 23. fast = getSum(fast); 24. fast = getSum(fast); 25. // 慢指针一次一步 26. slow = getSum(slow); 27. 28. // 快慢指针相遇，说明出现循环，不是快乐数 29. if (fast == slow){ 30. return false; 31. } 32. } 33. // 快指针走到1，是快乐数 34. return true; 35. }

该算法时间复杂度为O(logn)，空间复杂度为O(1)。