博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
<LeetCode OJ> 26 / 264 / 313 Ugly Number (I / II / III)
阅读量:6007 次
发布时间:2019-06-20

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

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.

分析:

题目说的非常清楚。所谓丑数,就是那些因子仅仅含2,3,5的数

那么依据丑陋数的定义,我们将给定数除以2、3、5,直到无法整除,也就是除以2、3、5的余数不再为0时停止
这时假设得到1,说明是全部因子都是2或3或5,假设不是1。则不是丑陋数。

class Solution {public:    bool isUgly(int num) {       if(num<=0)              return false;         if(num==1)              return true;                    while(num>=2 && num%2==0) //先将因子2除完,接着3,5            num/=2;          while(num>=3 && num%3==0)             num/=3;          while(num>=5 && num%5==0)             num/=5;                    return num==1;      }};

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:

  1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. 
  2. Try to focus your effort on generating only the ugly ones.

分析:

提示说的非常清楚,第n个丑数的沿途大量的数都不是丑数。为了能跳过对他们的推断

直接由小到大生成丑数进行统计个数,直到是第n个为止
用三个暂时数和数组来渐进增大丑数。

本质上以下这样的解法是动态规划,显然第n个丑数肯定是由前面某个丑数乘以2或者3或者5,

问题就在于生成的丑数要是有序的!

这可就麻烦了,三个指针总是维护*2*3*5的结果,他们总是下一个候选丑数!

令figure2是由某个较小丑数*2产生的新丑数,

令figure3是由某个较小丑数*3产生的新丑数,

令figure5是由某个较小丑数*5产生的新丑数,

第n个丑数肯定是三者中的较小者。可是必须得保证我们三者的生成规则。

三者的生成规则:

显然下一次的figure2。figure3。figure5必须比当前产生的丑数大。

那么就要求一旦当前产生的丑数大比三个候选丑数大就将其变大一点。从小到大沿途乘以2/3/5(详细看代码)

下面设计參考别人:

//首先思路:提示说的非常清楚,第n个丑数的沿途大量的数都不是丑数,为了能跳过对他们的推断//直接由小到大生成丑数进行统计个数。直到是第n个为止//用三个暂时数来渐进增大的丑数class Solution {public:    int nthUglyNumber(int n)     {        vector
ugly(n,0); ugly[0]=1; int figure2=2,figure3=3,figure5=5; int index2=0,index3=0,index5=0; for(int i=1;i

其它小伙伴的做法:

全部的ugly number都是由1開始。渐乘2/3/5一步一步生成。

仅仅要将这些生成的数排序就可以获得,自己主动排序能够使用set集
这样每次取出的第一个元素就是最小元素,由此再继续生成新的ugly number.
这样做有一个弊端,每次插入都有O(lg(N))的时间复杂度,所以比上一种方法慢。

class Solution {public:    int nthUglyNumber(int n) {        set
order;//最小堆(顶是最小值)同意反复数据存在。不能使用堆 order.insert(1); int count = 0; long long curmin = 0; while(count < n) { curmin = *(order.begin()); order.erase(order.begin()); order.insert(curmin * 2); order.insert(curmin * 3); order.insert(curmin * 5); count ++; } return (int)curmin; }};

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

分析:

方法和上面一题一样,仅仅只是因子多了几个而已。变量都取得一样。就不多解释了!

class Solution {public:    int nthSuperUglyNumber(int n, vector
& primes) { vector
ugly(n,0); vector
figures(primes); vector
indexs(n,0); ugly[0]=1; for(int i=1;i

參考资源:

【1】网友。。原文地址, http://blog.csdn.net/tyq101010/article/details/49256889

注:本博文为原创。兴许可能继续更新本文。

假设转载,请务必复制本条信息!

原文地址:http://blog.csdn.net/ebowtang/article/details/51581228

原作者博客:http://blog.csdn.net/ebowtang

:http://blog.csdn.net/ebowtang/article/details/50668895

你可能感兴趣的文章
MongoDB repl set权限认证配置步骤
查看>>
java学习笔记(1)
查看>>
禁止Mysql默认端口访问Internet - MySQL - IT技术网
查看>>
基于用户投票的排名算法(二):Reddit
查看>>
下午最后的草坪
查看>>
Maven学习总结(七)——eclipse中使用Maven创建Web项目
查看>>
1.部分(苹果)移动端的cookie不支持中文字符,2.从json字符串变为json对象时,只支持对象数组...
查看>>
HDU3257 Hello World!【打印图案+位运算】
查看>>
Node.js 抓取电影天堂新上电影节目单及ftp链接
查看>>
从设计者的角度看 React
查看>>
CSS居中总结大全
查看>>
Elasticsearch 参考指南(安装X-Pack)
查看>>
[LintCode] 604. Design Compressed String Iterator
查看>>
微信小程序黑客马拉松即将开始,来做最酷的 Mini Program Creators!
查看>>
JavaScript基础---函数
查看>>
前端每日实战:120# 视频演示如何用纯 CSS 创作锡纸撕开的文字效果
查看>>
Laravel实用小功能
查看>>
matplotlib绑定到PyQt5(有菜单)
查看>>
利用Powershell和ceye.io实现Windows账户密码回传
查看>>
Windows 8.1 今年 1 月市场份额超 Vista
查看>>