首页 > 其他分享 >【LeetCode哈希表#3】快乐数(set)

【LeetCode哈希表#3】快乐数(set)

时间:2023-01-30 21:45:19浏览次数:61  
标签:10 set int sum 快乐 哈希 LeetCode 循环

快乐数

力扣题目链接(opens new window)

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

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

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

示例:

输入:19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

初见思路

题意不难理解

步骤大致可以拆分成:

1、获取输入整数各位上的数

2、做平方后相加

3、重复上述过程

显然需要有一个循环计算的过程,那么结束条件是sum为1,但要是出现无限循环(sum一直不为1)的情况,那程序就卡死了

如何处理上述情况?

思路

本题的两个关键点:取各个数位上的单个数、循环结束条件

取各个数位上的单个数

先再次复习一下编程中的两种除法操作:取整取余(取模)

在c++中,

"/"是做取整数的除法,例如:19/10 = 1.9 = 1

"%"是做取除法但是取余数的值,例如:19%10 = 1余9 = 9

那么,可以先用10来和输入整数做取余运算来不断获取整数的个位数,然后通过取整运算将已经获取的数去除

如此循环到只剩下一位数,其再做除法得小数,经过取整后得0,此时循环结束

void getEechNum(int n) {
    int curNum;
    cout << "从个位开始的每个数为:" << endl;
    while (n) {//同时,以n作为循环结束条件
        curNum = n % 10;//获取当前个位上的数
        cout << curNum << endl;
        n /= 10;//去除已获取到的数
    }
}

int main() {
    getEechNum(156);
}

题中要求取到整数的每个单个数后做平方运算,因此用来取每个数的函数可以写成:

// 取数值各个位上的单数之和
int getSum(int n) {
    int sum = 0;
    while (n) {
        sum += (n % 10) * (n % 10);//直接在这里做平方运算
        n /= 10;
    }
    return sum;
}
循环结束条件

通过题目可知,“快乐数”的计算过程可能会出现无限循环的情况

例如,输入整数A,经过10次计算后sum = A

这就进入无限循环了,那么整数A也就不可能是快乐数

上述现象可以作为判断快乐数时循环结束的条件

具体处理上,我们可以让每次计算得到的sum保存到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
        unordered_set<int> set;
        //4、循环计算过程,知道找出快乐数或者陷入死循环
        while(1){
            //1、获取输入整数每各数位上的数的平方和
            int sum = getSum(n);
            //2、判断和是否为1
            if (sum == 1) {
                return true;
            }else if(set.find(sum) != set.end()){//如果sum值在set中出现过,则陷入循环
                return false;
            }else{
                set.insert(sum);
            }  
            //3、不为1则更新n值继续计算
            n = sum; //重复对sum进行上述运算 
        }
    
    }
};

标签:10,set,int,sum,快乐,哈希,LeetCode,循环
From: https://www.cnblogs.com/DAYceng/p/17077323.html

相关文章

  • LeetCode 删除链表的倒数第 N 个结点(/)
    原题解题目给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。约束题解方法一classSolution{public:intgetLength(ListNode*head){......
  • 【双指针】LeetCode 11. 盛最多水的容器
    题目链接11.盛最多水的容器思路在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽底边宽度−1:若向内移动短板,则\(min(h[i],h[j])\)可能变大,因此下个水槽的面......
  • leetcode简单(数组、字符串):[219, 268, 349, 414, 485, 541, 557, 821, 925, 977]
    目录219.存在重复元素268.丢失的数字349.两个数组的交集414.第三大的数485.最大连续1的个数541.反转字符串II557.反转字符串中的单词III821.字符的最短距离925......
  • 【算法训练营day31】LeetCode455. 分发饼干 LeetCode376. 摆动序列 LeetCode53. 最大
    LeetCode455.分发饼干题目链接:455.分发饼干独上高楼,望尽天涯贪心的思路,将每块饼干都发给最合适的孩子,那么最后分发饼干的策略就是最合适的,即可满足最多的孩子。class......
  • set -o pipefail
    对于set命令-o参数的pipefail选项,linux是这样解释的:“Ifset,thereturnvalueofapipelineisthevalueofthelast(rightmost)commandtoexitwithanon-zero......
  • [LeetCode] 1329. Sort the Matrix Diagonally 将矩阵按对角线排序
    A matrixdiagonal isadiagonallineofcellsstartingfromsomecellineitherthetopmostroworleftmostcolumnandgoinginthebottom-rightdirectionu......
  • LeetCode 31_下一个排列
    LeetCode31:下一个排列题目整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如,arr=[1,2,3],以下这些都可以视作arr的排列:[1,2,3]、[1,3,2]、[3,1,2......
  • DataSet用法详细
    DataSet用法详细一、特点介绍1、处理脱机数据,在多层应用程序中很有用。2、可以在任何时候查看DataSet中任意行的内容,允许修改查询结果的方法。3、处理分级数据4、缓存......
  • coredns mysql 扩展使用+readyset 试用
    基于db进行dns记录的管理还是比较有用的,尤其在一些开发环境中,以下是一个使用同时也会尝试集成readyset(但是木有成功,应该是mysql编码兼容的问题)添加&构建插件方法比较简......
  • readyset 轻量级pg 以及mysql 缓存引擎
    readyset是基于rust开发的pg以及mysql轻量级缓存服务参考玩法如下图  说明readyset一些设计还是很有意思的,很值得学习,同时也可以在项目中尝试使用参考资料​​https:/......