leetcode Ugly Number I II

leetcode 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.

题目地址: leetcode Ugly Number

题意:

Ugly numbers 是一个只能被2,3,5整除的数,给你一个数,判断是否是 ugly number

思路:

直接分别除2,3,5。。。看看最后是不是1

注意0的情况

C++

Java

Python

 

 

 


264. 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.

题目地址: leetcode Ugly Number II

题意:

Ugly numbers 是一个只能被2,3,5整除的数,求第n个Ugly number

思路:

我们来看看,要如何求第n个ugly number.

第一个ugly number 是1 我们讨论n大于1的情况

因为它只能被2,3,5整除,所以我们从1开始扩展,每次要么乘2,要么乘3,要么乘5.

对于1来说,我们分别乘以2,3,5得到[2,3,5],显然2是最小的。

于是第2个ugly number是2。

接着第3个呢?显然是 3 . 从 1 * 3 得到

第4个就不一样了,它是从2*2得到。

这有什么规律呢?规律就是,每个因子分别乘以当前得到的ugly number(初始为1),当某因子x算出来的不大于其他两个因子,说明新的ugly number是当前因子算出来的,下一轮,该因子应该乘以之前ugly number的下一个。

换句话说,每个因子分别乘以对应的ugly number[i]后,如果得到了新的ugly number 就说明下一次应该乘以下一个(ugly number[i+1])。这样能保证乘出来的小而且不会漏掉。

详见代码:

Java

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Ugly Number I II
本文地址:https://www.hrwhisper.me/leetcode-ugly-number-i-ii/

您的支持将鼓励我继续创作!

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *