即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

剑指offer 34题-丑数

编程语言 h2011059150007 13℃ 0评论

丑数,指的是只包含因子为2,3,5的数,一般称1是第一个丑数,经常有道面试题,求第N个丑数

看完剑指offer的解释,我把两种方法总结下:

第一种方法,简单粗暴,就是从0开始,对每一个数字判断他是否是丑数,直到N个为止,这种方法时间效率较低

   两个函数,第一个判断一个数是否为丑数,第二个就是从找到第N个丑数

第一个函数:

  判断一个数是否为丑数,有一个很简单,但第一次很难想出的方法,我也是看完才知道这么简洁,精炼的办法:根据丑数的定义,丑数只能被2,3,5整除,假设num为丑数,如果能被2,3,5整除,就将他们除以2,3,5。除到最后num为1,则是丑数,否则不是。这里稍微难理解的就是,如果如果能被2,3,5整除,就将他们除以2,3,5;看看具体代码就清楚了


 bool IsUgly (int num)

{

   while(num%2 ==0)

    num=num/2;

  while (num%3 ==0)

   num=num/3;

 while (num%5==0)

  num=num/5;

  return num ==1 ? true:false;

}

转载请注明:CodingBlog » 剑指offer 34题-丑数

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情