leetcode@ [263/264] Ugly Numbers & Ugly Number II

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

https://leetcode.com/problems/ugly-number/

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

class Solution {
public:
bool isUgly(int num) {
if(num <= ) return false;
if(num == ) return true; while(num% == ){
num/=;
if(num == ) return true;
}
while(num% == ){
num/=;
if(num == ) return true;
}
while(num% == ){
num/=;
if(num == ) return true;
}
return false;
}
};

leetcode 263: Ugly Numbers

https://leetcode.com/problems/ugly-number-ii/

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

class Solution {
public:
int nthUglyNumber(int n) {
if(n <= ) return n; vector<long long> dp(n+, );
for(int i=;i<=;++i) dp[i] = i; for(int i=;i<=n;++i) {
long long Min = numeric_limits<long long>::max();
for(int pre=;pre<=i-;++pre) {
if(dp[pre]* > dp[i-]) {Min = min(Min, dp[pre] * ); continue;}
else if(dp[pre] * > dp[i-]) {Min = min(Min, dp[pre] * );continue;}
else if(dp[pre] * > dp[i-]) Min = min(Min, dp[pre] * );
}
dp[i] = Min;
} return dp[n];
}
};

leetcode 264: Ugly Numbers II

leetcode@ [263/264] Ugly Numbers & Ugly Number II的更多相关文章

【Leetcode】【Medium】Single Number II
Given an array of integers, every element appears three times except for one. Find that single one. ...
【leetcode刷题笔记】Single Number II
Given an array of integers, every element appears three times except for one. Find that single one. ...
136 - Ugly Numbers
Ugly Numbers Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3 ...
leetcode 263&period; Ugly Number 、264&period; Ugly Number II 、313&period; Super Ugly Number 、204&period; Count Primes
263. Ugly Number 注意:1.小于等于0都不属于丑数 2.while循环的判断不是num >= 0, 而是能被2 .3.5整除,即能被整除才去除这些数 class Solution ...
[LeetCode] 264&period; Ugly Number II 丑陋数之二
Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors ...
[LeetCode] 264&period; Ugly Number II 丑陋数 II
Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors ...
Leetcode之动态规划（DP）专题-264&period; 丑数 II（Ugly Number II）
Leetcode之动态规划(DP)专题-264. 丑数 II(Ugly Number II) 编写一个程序,找出第 n 个丑数. 丑数就是只包含质因数 2, 3, 5 的正整数. 示例: 输入: n ...
【LeetCode】264&period; Ugly Number II
Ugly Number II Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose ...
[leetcode] 264&period; Ugly Number II (medium)
263. Ugly Number的子母题题目要求输出从1开始数,第n个ugly number是什么并且输出. 一开始想着1遍历到n直接判断,超时了. class Solution { public: ...

随机推荐

Android 隐式意图的配置
本文地址:http://www.cnblogs.com/wuyudong/p/5677473.html,转载请注明源地址. <Android 显示意图激活另外一个Actitity>一文介绍 ...
1021上课演练----SQL注入与避免（银行系统）
package com.bank; import java.sql.CallableStatement; import java.sql.Connection; import java.sql.Dat ...
[转]Gridview中实现RadioButton单选效果
HTML <asp:TemplateField ItemStyle-Width="22px"> <ItemTemplate> <asp:RadioBu ...
JavaScript高级程序设计18&period;pdf
系统对话框 alert().confirm()和prompt()调用系统对话框向用户显示消息,显示对话框的时候代码会停止执行,关闭后继续执行 alert()警告提示框 confirm()点击确认返回t ...
学会查看Linux手册页（man文档）
区段1:用户指令区段2:系统调用区段3:程序库调用区段4:设备区段5:文件格式区段6:游戏区段7:杂项区段8:系统指令区段9:内核内部指令区段n:Tcl或Tk指令如果记不清楚工具或者函数的完整名字, ...
CentOS7&period;5安装Tomcat8
一.tomcat的简介这是Apache Tomcat Servlet / JSP容器的文档包的顶级入口点 .的Apache Tomcat 8.0版实现了Servlet 3.1和JavaServer ...
maven 骨架命令行创建
项目的骨架maven 约定在项目的根目录下放置pom.xml,在src/main/java目录下放置主代码,在src/test/java下放置项目的测试代码. 这些基本的目录结构和pom.xml文件的 ...
JFinal的启动源码解读
本文对Jfinal的启动源码做解释说明. PS:Jfinal启动容器可基于Tomcat/Jetty等web容器启动,本文基于Jetty的启动方式做启动源码的解读和分析,tomcat类似. 入口 JF ...
Centos7 Python3&period;x源码安装
第一步,安装开发工具集 yum -y groupinstall "Development tools" 第二步,安装相关依赖包: yum -y install zlib-devel ...
node的close
在http.ServerResponse对象的end方法被调用之前,如果连接被中断,将触发http.ServerResponse对象的close事件. var http=require("h ...