首页 > 其他分享 >202. 快乐数

202. 快乐数

时间:2023-12-18 18:26:23浏览次数:25  
标签:getNext arr 202 return int sum 244 快乐

题目

202. 快乐数

要求

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

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

思路

这道题目我没有思路,该怎么说呢,数据归纳法,看到下面这组数据:

Digits Largest Next
1 9 81
2 99 162
3 999 243
4 9999 324
13 9999999999999 1053

可以看到的是无论多大的数字,最后经过计算总会回归到 3 位数,例如 9999 的下一个是 324,而 999 最后是 243,也就是说最后只有两种情况,一种是得到快乐数,最后结果是 1,另外一种就是无限循环,但是是在 243 以下循环,基于此,可以考虑使用递归的方法,看看结果如果是 1 或者之前出现过,那说明出现了环,就退出:

public boolean isHappy(int n) {
    int[] arr = new int[244];
    return myIsHappy(n, arr);
}

public boolean myIsHappy(int n, int[] arr) {
    if (n == 1) {
        return true;
    }
    if (n < 244 && arr[n] == 2) {
        return false;
    }
    int sum = getNext(n);
    if (sum < 244) {
        arr[sum]++;
    }
    return myIsHappy(sum, arr);
}

public int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        n /= 10;
        sum += d * d;
    }
    return sum;
}

看到环,能想到啥,链表呀,这个可以看做是一个链表,要么结果为 1,要么是链表成环,可以使用一个数组做一个缓存,因为快慢指针肯定有计算过的,防止重复计算,代码如下:

public boolean isHappy(int n) {
    // arr 加一层缓存,防止计算 next 的时候重复计算
    int[] arr = new int[244];
    int slow = n;
    int fast = getNext(n, arr);
    while (fast != 1 && fast != slow) {
        slow = getNext(slow, arr);
        fast = getNext(getNext(fast, arr), arr);
    }
    return fast == 1;
}

private int getNext(int n, int[] arr) {
    if (n < 244 && arr[n] != 0) {
        return arr[n];
    }
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        n /= 10;
        sum += d * d;
    }
    if (n < 244) {
        arr[n] = sum;
    }
    return sum;
}

标签:getNext,arr,202,return,int,sum,244,快乐
From: https://www.cnblogs.com/wadmwz/p/17911862.html

相关文章

  • 20231218打卡
    今天考完了java期末测试,50分得了37分,主要扣在了财务统计和审批查询上,同时,今天的考试也不同于以往的练习,不再对USER进行CRUD操作,我是踩了这个坑的,浪费了好多时间,然后我对于业务流程的审批处理操作不够熟悉,在剩余的时间也只完成了大部分的内容。分清楚项目需求真的非常关键且必要,希......
  • 2023年国家基地“楚慧杯”网络安全实践能力竞赛初赛-Crypto+Misc WP
    Miscez_zip题目4096个压缩包套娃我的解答:写个脚本直接解压即可:importzipfilename='附件路径\\题目附件.zip'foriinrange(4097):f=zipfile.ZipFile(name,'r')f.extractall(pwd=name[:-4].encode())name=f.filelist[0].filenameprint(nam......
  • 《2022雷军年度演讲全文:穿越人生低谷的感悟》
    参考:2022雷军年度演讲全文:穿越人生低谷的感悟首先,本次演讲我认为是相比以往很不一样的。雷军讲述了自己职业生涯三次低谷,以及面对人生挫折的复盘,可谓是干货满满。另外演讲的过程中不难看出,他的心中永远保持着梦想和热爱,即使过程并不顺利但依然坚持思考,乐观面对,这种力量是直击人心......
  • 云原生周刊:Kubernetes v1.29 正式发布 | 2023.12.18
    开源项目推荐RobustaKRRRobustaKRR(KubernetesResourceRecommender)是一个用于优化Kubernetes集群中资源分配的CLI工具。它从Prometheus收集Pod使用数据,并建议CPU和内存的请求和限制。这降低了成本并提高了性能。LiqoLiqo是一个开源项目,可实现动态、无缝的Kuber......
  • 2023-12-18 每天一练
    LeetCode每日一题162.寻找峰值问题峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。你可以假设nums[-1]=nums[n]=-∞。你必须实现时间复杂度为O(log......
  • 《产品平台和CBB管理高级实务》公开课(深圳2024年1月12-13日)
    【课程收益】解决的关键问题:在研发体系建设、研发管理,以及产品开发过程中,研发管理人员、系统工程师、项目经理等通常会面临以下问题,希望通过本课程的学习,能够为以上人员提供具体的解决思路和应对措施。①.   为了满足不同用户的需求,长期积累下来的产品型号和物料种类繁......
  • 1 K8S for Prometheus Dashboard 20211010 EN
    *[PrometheusTimeSeriesCollectionandProcessingServer](http://localhost:9090/targets?search=#pool-prometheus)*[Dashboards|GrafanaLabs](https://grafana.com/grafana/dashboards/?search=prometheus)*[Alertmanager|GrafanaLabs](https://grafana.com/g......
  • 零数科技双平台入选2023爱分析·数据要素流通厂商全景报告
    全面近日,国内领先的数字化市场研究咨询机构爱分析正式发布《2023爱分析·数据要素流通厂商全景报告》,零数科技凭借成熟的区块链和隐私计算技术,及系列标杆产品及应用,成功入选数据要素流通代表厂商。图:零数科技入围爱分析数据要素厂商全景地图随着数字经济的崛起,数据成为推动社会生产......
  • 活动预告 | 2023CCF中国区块链技术与应用高峰论坛议程发布
    党的二十大报告明确提出要建设数字中国,加快发展数字经济。区块链作为数字经济的重要支撑技术,在不同行业领域中已得到了广泛应用,并深度赋能社会和经济发展。为进一步加快区块链技术与应用深度结合,促进区块链产业发展,驱动区块链更好赋能数字经济,由中国计算机学会(CCF)主办,CCF区块链专业......
  • 2021-CVPR-Transformer Tracking
    TransformerTracking相关性在跟踪领域起着关键作用,特别是在最近流行的暹罗跟踪器中。相关操作是考虑模板与搜索区域之间相似性的一种简单的融合方式。然而,相关操作本身是一个局部线性匹配过程,导致语义信息的丢失并容易陷入局部最优,这可能是设计高精度跟踪算法的瓶颈。还有比相关......