丑数

  1. https://leetcode-cn.com/problems/ugly-number/
  2. 判断一个数不是丑数难，但是判断一个数是否是丑数简单。 
    1
2
3
4
5
6
7

    for i = 2,3,5
    while(num % i == 0)
        num = num/i
if(num == 1)
    return true;
else 
    return false;

丑数Ⅱ

  1. https://leetcode-cn.com/problems/ugly-number-ii/
  2. 三指针法

超级丑数

  1. https://leetcode-cn.com/problems/super-ugly-number/
  2. 思路和上一题一样，只不过不再是三个指针了，有几个质数就需要几个指针！

丑数Ⅲ

  1. https://leetcode-cn.com/problems/ugly-number-iii/
  2. 这道题目中的“丑数”和前面几道题的定义都不同，定义更简单了，因为只要求能被三个数之一整除即可。
  3. 暴力求解法就是一个个数尝试，因为验证是否是丑数很简单的。但是这样会超出时间限制。
  4. 所以需要进行优化，优化的思路真的可以说是一个纯数学的思路了！
    • 这道题目的关键点在于二分法，而二分法的切入点又在于确定一个整数 k 究竟是第几个丑数。
    • 想知道一个数 k 是第几个丑数需要先确定 k 包含了多少个丑数因子，确定数 k 有 x 个丑数因子之后，就可以找出第 x 个丑数是多少了。
  5. 确定一个数有多少个丑数因子
    1. 该数只能被a整除 (该数一定是a 的整数倍)
    2. 该数只能被b整除 (该数一定是b 的整数倍)
    3. 该数只能被c整除 (该数一定是c 的整数倍)
    4. 该数只能被a和b同时整除 (该数一定是a、b最小公倍数的整数倍)
    5. 该数只能被a和c同时整除 (该数一定是a、c最小公倍数的整数倍)
    6. 该数只能被b和c同时整除 (该数一定是b、c最小公倍数的整数倍)
    7. 该数只能被a和b和c同时整除（该数一定是a、b、c的最小公倍数的整数倍）
  6. 辗转相除法也被称为除余法！(只和除数以及余数有关系)
  7. 根据有 n 个丑数因子的数 k， 找到第 n 个丑数 x：x=k−min(k