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

Example 1:

1
2
3
Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

1
2
3
Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

1
2
3
Input: 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

  1. 1 is typically treated as an ugly number.

  2. Input is within the 32-bit signed integer range: [−2^31, 2^31 − 1].

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。


思路

  • 丑数就是因子不能包含除了2,3,5以外的数,1也是丑数。

  • 从2开始,将n除以2,一直除到不包含2这个因子为止;然后开始整除3;开始整除5;最后将2,3,5三个因子除尽,丑数必为1,判断是否为1即可。

  • 可以直接写成for(int i=2;i<=5;i++),里面包含4,因为4可以拆成2*2,不影响丑数的定义。

C++ code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isUgly(int num) {
for(int i=2;i<=5&&num;i++)
{
while(num%i==0)
num/=i;
}
return num==1;
}
};

第二题

找到第n个丑数

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

1
2
3
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  1. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.

思路

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

  2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

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

  4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 2, L2 3, L3 * 5).

细节

  • uglynum容器中的每一个数都要经过2,3,5的洗礼,取到接受洗礼的数中最小的一个作为勇者并放入丑数容器中。如果被选中的勇者是经过2洗礼的,那么就让2取洗礼容器中的下一个数,所以2的指针++
  • 为什么不用if else判断呢,因为在选中最小的数中,是最小公倍数,所以有可能因子包含2,3,5,所以只要判断是不是当前指针所指数的倍数就好,如果是的话,就要洗礼丑数容器中的下一个数。

C++ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<=6)return index;
vector<int> a;
a.push_back(1);
int t2=0,t3=0,t5=0;
while(a.size()<index)//这里不能用等号
{
a.push_back(min(min(a[t2]*2,a[t3]*3),a[t5]*5));//此时预演,指针还没有动
//判断新加入的丑数是不是当前每个因子指针的倍数,如果是的话,就往前移动一格,说明已经对旧丑数做了乘以因子的处理了
if(a.back()==a[t2]*2) t2++;
if(a.back()==a[t3]*3) t3++;
if(a.back()==a[t5]*5) t5++;//这里千万不能用if else啊!!
}
return a.back();
}
};

总结

  • 关键点是维护好丑数的顺序,融合三个有序序列的最小值,这个最小值加入到丑数数组中,也是有序的。

  • 因为丑数数组是一个有序的的数组,想到用DP来解决,DP的精髓就是把大问题分解成小问题,而且要保存小问题的解。怎么保存呢,可以开三个数组,但是用指针会更方便。本题用三个指针,以下标的形式,a[t2],a[t3],a[t5],来分别指向丑数容器中要乘以2,3,5的数。

  • 最新的丑数就是在这三个指针所指的数上再分别乘以2,3,5后,其中的最小一个。新的丑数中可能也还有别的两个因子,所以要判断是否是其他因子的倍数,然后移动相关的指针,注意每个因子都要判断。

Thanks for Support.