前言

本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!

算法题(LeetCode刷题202快乐数)—(保姆级别讲解)

力扣题目链接

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题202快乐数) 2023.5.9-LMLPHP

分析题目

  1. 题目中说了会无限循环,那么也就是说在求和过程中,sum会重复出现,则我们可以联想到可以通过判断sum这个元素是否出现在集合里,如果sum重复出现了,则代表该数肯定不是快乐数,即我们可以联想到哈希法来判断。
  2. 既然我们选择用哈希法来判断,则我们需要选择使用哪种数据结构来构建哈希表,由于最终集合里是保证元素不能重复,所以我们采用unordered_set

算法思想(使用unordered_set实现哈希表)

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;
        }
    }
};

好!按照老样子,接下来开始详细讲解每行代码的用处,以及为什么这样写

int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

这个函数的作用是取得数值各个位上的单数平方之和。那么重点肯定是如何求得各个位的数值。

在这里举个例子,假设n = 123,则我们取得个位的方法为n%10,即123%10 = 3,那么在下一次取得十位的方法为n/10,即123/10 = 12,以此类推,12%10 = 212/10=11%10 = 11/10 = 0。至此,退出while循环。

unordered_set<int> set;

由于我们选择使用unordered_set实现哈希表,即为我们最终遍历的集合,该集合名称为set

int sum = getSum(n);

获得了该每一位的平方和,并且赋值为sum

if (sum == 1) {
                return true;
            }

如果直接求和之后等于1,即代表为快乐数,不用再迭代了,直接返回。

if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }

unordered_set::find()函数是C++ STL中的内置函数,用于在容器中搜索元素。如果找到指定元素,它返回元素的迭代器,如果找不到指定元素,则返回指向unordered_set::end()的迭代器。所以判断与set.end()是否相等即可。

如果不相等,则代表集合中有相同的元素,即代表sum重复了,则代表该num肯定不是快乐数。

如果相等,则代表找不到指定元素,则我们为了再下一次循环迭代过程中,比较sum值,我们需要将该sum值添加到集合set中。

 n = sum;

sum赋值给n,方便下一次计算新的sum值。

结束语

如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!

05-09 22:59