LeetCode 202. 快乐数

2020-04-30 16:11:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LeetCode 202. 快乐数

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 202. 快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为? 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  • 比较容易想到的是顺序计算并判断,因为可能存在循环,所以再额外需要set来保存计算过的值用以后续验重;
  • 另一种思路是快慢指针,因为快乐数的计算最终只会有两种结果:
    • 进入1循环;
    • 进入某循环链无终止循环;
  • 纯数学分析规律,对上面思路更清晰化的解释,即最终的循环结果:
    • 进入1循环;
    • 进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 循环链;

纯数学的分析优化的是非快乐数的循环链,有了链就可以直接建立速查表避免了边计算边存数

思路1-按步骤计算用set保存每次计算结果;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(logn\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(logn\right)}} $

思路2-建立快慢指针

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(logn\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-数学分析规律建立速查表

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(logn\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

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

原文链接:https://www.cnblogs.com/izhoujie/p/12581093.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Intellij IDEA Debug 调试技巧

下一篇:Springboot整合微信小程序实现登录与增删改查