最新消息:

Is Perfect Number 完美数(esay)

算法 ksharpdabu 253浏览 0评论

Good morning! Here’s your coding interview problem for today.

This problem was asked by Microsoft.

A number is considered perfect if its digits sum up to exactly 10.

Given a positive integer n, return the n-th perfect number.

For example, given 1, you should return 19. Given 2, you should return 28.

题目意思:所谓perfect number ,指一个正整数,如果这个数的每一位数字加起来等于10。第一个perfect number是19 (1+9=10),第二个是28(2+8=10)。要求你写个函数能够返回第n个perfect number。

solution:

方法一:暴力查找

直接从start=19开始计算,每次判断下是否为完美数字,如果是,则count++  ,然后start+1,进行下次判断。

 

方法二:增加步长,提高效率

方法一中start++的方式,比较慢。我们可以每次start= start+9 ,这样会快很多。如下:

 

注意:
1.这里虽然每次可以+9,但是有个问题,比如假设到271, 280, 下一个完美数就并不是289。网上不少人写的算法有这个问题,认为可以直接通过n而不需要count变量来得到第n个完美数。这就是问题的关键点,我们找不到一个公式将完美数与n直接关联上,必须通过count来计数,从count=0一直累加到count= n。否则,我们只能保证算法返回的是完美数,但是这个数很可能并不是第n个原文的方法三就是个错误的算法,我在最后面的测试代码中有对比
2.步长不仅可以是9,其实也可以是10。从0开始,每次加10,此时start=10 ,start/10=1,   此时每个位数字和位1,则末尾就是10-1=9,第一个完美数就是19, start=19+10 ,  29/10=2  ,则末尾就是10-2=8 ,第二个完美数就是28。如果上一个完美数是280,则(280+10)/10=29 , 2+9>10 , 所以继续加10:290+10=300 ,300/10=30 ,则末尾就是10-3-0=7 ,这个完美数就是307 ,依次类推。这里9比10好,就是因为加9刚好让低位减少1,高位+1,再大多数情况下,+9都能直接得到完美数,不用再推算最后一位的值。
下面是完整的代码,增加了对数器来用生成测试用例,检测算法是否正确:

 

原文:

转载请注明:大步's Blog » Is Perfect Number 完美数(esay)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址