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)。
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)。
