博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Leetcode: Ugly Number II
阅读量:5294 次
发布时间:2019-06-14

本文共 1627 字,大约阅读时间需要 5 分钟。

Write a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.Note that 1 is typically treated as an ugly number.Hint:The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

参 Lintcode:

注意12-14行千万不要写成else if,因为如果同时两个Pointer比如 twoPointer and threePointer 都满足得到最小,两个pointer都要+1

1 public class Solution { 2     public int nthUglyNumber(int n) { 3         ArrayList
res = new ArrayList
(); 4 if (n <= 0) return Integer.MIN_VALUE; 5 res.add(1); 6 int twoPointer = 0; 7 int threePointer = 0; 8 int fivePointer = 0; 9 for (int i=2; i<=n; i++) {10 int min = Math.min(Math.min(res.get(twoPointer)*2, res.get(threePointer)*3), res.get(fivePointer)*5);11 res.add(min);12 if (min/res.get(twoPointer) == 2) twoPointer++;13 if (min/res.get(threePointer) == 3) threePointer++;14 if (min/res.get(fivePointer) == 5) fivePointer++;15 }16 return res.get(n-1);17 }18 }

 

转载于:https://www.cnblogs.com/EdwardLiu/p/5068745.html

你可能感兴趣的文章
Codeforces 962 /2错误 相间位置排列 堆模拟 X轴距离最小值 前向星点双连通分量求只存在在一个简单环中的边...
查看>>
Matrix快速幂 模板
查看>>
MySQL开启远程连接权限
查看>>
tomcat7.0.27的bio,nio.apr高级运行模式
查看>>
C#预处理器命令
查看>>
苹果手表:大方向和谷歌一样,硬件分道扬镳
查看>>
Competing Consumers Pattern (竞争消费者模式)
查看>>
HDUOJ ------1398
查看>>
cf--------(div1)1A. Theatre Square
查看>>
Android面试收集录15 Android Bitmap压缩策略
查看>>
PHP魔术方法之__call与__callStatic方法
查看>>
ubuntu 安装后的配置
查看>>
Html学习_简易个人网页制作
查看>>
angular中ng-bind指令小案例
查看>>
jqery总结
查看>>
Lodop获取客户端主网卡ip地址是0.0.0.0
查看>>
VSCODE更改文件时,提示:EACCES: permission denied的解决办法(mac电脑系统)
查看>>
web前端之路,js的一些好书(摘自聂微东 )
查看>>
【模板】对拍程序
查看>>
微信小程序开发初体验
查看>>