php网站编程,wordpress 导入演示,山西seo顾问,杭州做网站的公司哪些比较好1、题目 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为#xff1a;对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和#xff0c;然后重复这个过程直到这个数变为 1#xff0c;也可能是 无限循环 但始终变不到 1。如果 可以变为 1对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果 可以变为 1那么这个数就是快乐数。 如果 n 是快乐数就返回 True 不是则返回 False 。 2、思考分析
对一个数不断进行get_sum操作那么最终可能的结果有两种可能: 1、得到1 2、计算的数陷入某种循环然后会有重复的数出现 如果得到1直接返回true 如果检测到重复数出现就返回false 否则记录出现的数并在while循环中对n进行更新。 int get_sum(int n)
{int sum0;while(n!0){sum(n%10)*(n%10);n n/10;}return sum;}3、哈希法解
class Solution {
public:int get_sum(int n){int sum0;while(n!0){sum(n%10)*(n%10);n n/10;}return sum;}bool isHappy(int n) {int sum0;//sumsum出现的频次unordered_setint set;while(1){sumget_sum(n);if(sum 1) return true;//如果某个数重复出现那么我们认为此时陷入了循环则这个数不是快乐数else if(set.find(sum)!set.end()){return false;}set.insert(sum);nsum;}}
};4、双指针解 我们得到的结果序列是一个隐式的链表。 隐式意味着我们没有实际的链表节点和指针但数据仍然形成链表结构。 于是这个问题可以转换为检测一个链表是否有环。 这个问题可以使用快慢指针法来解决。我们不是只跟踪链表中的一个值而是跟踪两个值称为快跑者和慢跑者。在算法的每一步中慢速在链表中前进 1 个节点快跑者前进 2 个节点。 前进一次调用一次计算函数前进两次调用两次计算函数。
class Solution {
public:int get_next(int n){int sum0;while(n!0){sum(n%10)*(n%10);n n/10;}return sum;}bool isHappy(int n) {int sum0;int slow_runner n;int fast_runner get_next(n);while( fast_runner ! 1 slow_runner ! fast_runner){//更新slow_runnerslow_runner每次前进一步slow_runner get_next(slow_runner);//更新fast_runnerfast_runner每次前进二步所以调用两次getnext函数fast_runner get_next(get_next(fast_runner));}if(fast_runner 1) return true;return false;}
};
