leetcode202-快乐数

原题

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

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

示例:

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

解法

思想

递归求解,当每一位上的数字的平方之和为1时返回true,否则递归计算其和。不是1的和可以计入哈希集中,避免重复遇到。

代码

class Solution {
    Set<Integer> set = new HashSet<>();

    public boolean isHappy(int n) {
        int sum = 0;
        char[] nums = String.valueOf(n).toCharArray();
        int num = 0;
        for(char i:nums){
            //获取每一位上的数字
            num = i-48;
            sum += num * num;   
        }
        if(sum==1) return true;
        if(set.contains(sum)) return false;
        set.add(sum);
        return isHappy(sum);
    }
}
func isHappy(n int) bool {
    return isHappySub(n, map[int]bool{})
}

func isHappySub(n int, m map[int]bool) bool {
    if n == 1{
        return true
    }
    if res, ok := m[n]; ok{
        return res
    }
    count := 0
    temp := n
    for temp > 0{
        count += (temp%10)*(temp%10)
        temp = temp/10
    } 
    if count != 1{
        m[n] = false
    }
    return isHappySub(count, m)
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode202-%e5%bf%ab%e4%b9%90%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月17日
下一篇 2019年12月19日

相关推荐

  • leetcode61-旋转链表

    原题 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->…

    算法 2019年12月17日
    0110
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode779-第K个语法符号

    原题 在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。 给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始) 例子: 输入: N…

    算法 2020年1月22日
    0110
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • 拉帮结派的数据结构-并查集

    本文参考资源: 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构,又叫“不相交集合”,保持了一组不…

    2020年2月17日
    0140
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    080
  • leetcode169-多数元素

    原题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例1:…

    算法 2020年2月5日
    090

发表回复

登录后才能评论