编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回 false 。
示例:
输入:19 输出:true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
来源:力扣(leetcode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
纯数学的分析优化的是非快乐数的循环链,有了链就可以直接建立速查表避免了边计算边存数
算法复杂度:
算法复杂度:
算法复杂度:
package leetcode; import java.util.arrays; import java.util.hashset; /** * @author zhoujie * @date 2020年4月30日 下午10:24:08 * @description: 202. 快乐数 * */ public class leetcode_0202 { } class solution_0202 { /** * @author: zhoujie * @date: 2020年4月30日 下午10:53:37 * @param: @param n * @param: @return * @return: int * @description: 快乐数计算 * */ private int happyhelper(int n) { int temp = 0; while (n > 0) { temp += (n % 10) * (n % 10); n /= 10; } return temp; } /** * @author: zhoujie * @date: 2020年4月30日 下午10:24:31 * @param: @param n * @param: @return * @return: boolean * @description: 1-每次计算后,若为1则是快乐数,否则看是否在set,在则不是快乐数,不在则继续循环计算;(循环有限的,所以代码最后的return其实永远不会执行) * */ public boolean ishappy_1(int n) { hashset<integer> nohappy = new hashset<integer>(); while (n != 1 && !nohappy.contains(n)) { nohappy.add(n); n = happyhelper(n); } return n == 1; } /** * @author: zhoujie * @date: 2020年4月30日 下午10:36:06 * @param: @param n * @param: @return * @return: boolean * @description: 2-快慢指针;原理:若为1退出循环;若有环,则快指针最终会追上慢指针(多一个循环); * */ public boolean ishappy_2(int n) { int slow = n, fast = happyhelper(n); while (slow != fast) { if (slow == 1 || fast == 1) { return true; } else { slow = happyhelper(slow); fast = happyhelper(happyhelper(fast)); } } return slow == 1; } /** * @author: zhoujie * @date: 2020年4月30日 下午10:45:26 * @param: @param n * @param: @return * @return: boolean * @description: 3-数学规律,任意数最终会进入两个循环,一个是:1自身循环,一个是: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 * */ public boolean ishappy_3(int n) { // 建立不快乐数的最终循环自查表 hashset<integer> nohappy = new hashset<integer>(arrays.aslist(4, 16, 37, 58, 89, 145, 42, 20)); while (n != 1 && !nohappy.contains(n)) { n = happyhelper(n); } return n == 1; } }
如对本文有疑问, 点击进行留言回复!!
详解SpringBoot修改启动端口server.port的四种方式
网友评论