首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

LeetCode笔记:202. Happy Number

一看到这个题目我是懵逼的,看一个数字是不是happy,出题人真有童心。想找规律吧算了几个数字感觉没得规律找啊。从最简单的思路来看就是不断循环看最后得到的是不是1了,但是返回true的判断容易,什么时候就可以下结论说这个数字不happy呢?这才是问题。首先我们得到的数不知道是几位数,但是经过计算后最后肯定会变成个位数,而如果这个个位数是1那就是happy了,如果不是1应该就是不happy吧。所以我一开始的做法是循环求平方和,直到结果是个位数了就看是不是1来给出结果,这里还用到了一个递归,如果计算一次平方和还不是个位数就继续递归计算。 提交后发现有个错误,那就是1111111这个数,也是一个happy数字,但我判断为不是了。我数了一下一共七个1,平方和是7,才知道原来到了个位数后还会继续计算,我算了一下发现7还真能最后算出1来,那只能对于1~9九个个位数都看看是不是能算出1来了,算了一下觉得太麻烦了,于是想到了一个简单的方法,leetcode是可以自定义测试用例的,勾选Custom Testcase就可以了,然后我把4~9都试了一遍,不用试2、3是因为就等于4、9,测完发现只有1和7是的,所以在代码里把7也算成true就可以了。 最后的时间是4ms,还不错,看了看discuss也没有看到特别好的方法,那大抵就是这样了吧。

03

剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过数组长度的一半。这种方法的时间复杂度为O(n^2),在面试中,第一反应想到的方法往往不是最佳答案,下面我们来寻求更加高效的方式。 一个数出现的次数如果超过数组长度的一半,那么可以得出以下结论: 1.如果把超过数组长度一半的数整理在一起形成数组b,那么不管把b放在数组的什么位置,数组的中位数一定在b中。 2.个数超过数组长度一半的数最多只有一个。

06
领券