丑数与快速幂

丑数1，判断是否是丑数
除了对非正整数的判断，就是将2，3，5质因数从数字中抽取出来，然后看数字里如果只剩下1，那么就是丑数，否则就不是丑数，能除就做除，不能做除就判断。
其实是把每个需要判断的数字看成2^x13^x25^x3 就是丑数。
两种方式

class Solution:
    def isUgly(self, n: int) -> bool:
        if 1<=n<=3:
            return True

        if n<=0:
            return False
        # while n%2==0:
        #     n=n/2
        # while n%3==0:
        #     n=n/3
        # while n%5==0:
        #     n=n/5
        # return n==1

        for i in [2,3,5]:
            while n%i==0:
                n/=i
        return n==1

快速幂，这里想说代码形式和这个丑数有点像，只不过快速幂只除2，所以可以将n%2改为n&1，n/2改为n>>1,其实这里也可以将他理解成把幂中的2抽取出来，然后底数做乘积。当然了，在奇数的时候不做平方，只是单个数字。
其实也是将幂看作2^(x1+x2+x3)的形式
见链接https://blog.nowcoder.net/n/a99801191c8747c481636efc69c1f470

class Solution:
    def Power(self, base, exponent):
        # write code here
        result=1
        if base==0 and exponent<=0:
            return None
        if base==0:
            return 0

        if exponent<0:
            exponent=-exponent
            base=1/base
        while exponent>0:
            if exponent&1!=0:
                result*=base

            base=base*base
            exponent=exponent>>1

        return result

丑数2 找到第n个丑数。从下到上进行计算。

丑数的递推性质：丑数只包含因子 2, 3, 5，因此有 “丑数 == 某较小丑数 × 某因子” （例如：10 = 5 * 2）。

作者：jyd
链接：https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在已有的丑数序列上每一个数都必须乘2，乘3，乘5，这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, ..., n1, n2], 如果单纯的让每个丑数乘2，乘3，乘5顺序排列的话肯定会有问题，

比如如果按照这样的顺序排列下去肯定有问题[12, 13, 15, 22, 23, 25, 32, 33, 35, ... , n1 *2, n1 * 3, n1 * 5, n2 * 2, n3 3, n2 * 5]，因为后面乘2的数据可能会比前面乘3乘5的数据要小，那这个乘2的数应该排在他们的前面，后面乘3的数据也可能比前面乘5的数据要小，那这个乘3的数应该排在他们的前面。

那怎么办呢，每个数都必须乘2，乘3，乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序，这个改如何同时实现呢？

通过观察网上的各个题解，终于找到了办法，那就是记录每个丑数是否已经被乘2，乘3，乘5了，具体的做法是

设置3个索引a, b, c，分别记录前几个数已经被乘2，乘3，乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数；

对于某个状态下的丑数序列，我们知道此时第a个数还没有乘2(有没有乘3或者乘5不知道），第b个数还没有乘3(有没有乘2或者乘5不知道），第c个数还没有乘5(有没有乘2或者乘3不知道), 下一个丑数一定是从第a丑数乘2，第b个数乘3，第c个数乘5中获得，他们三者最小的那个就是下个丑数。

求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2得到的，还是某个数乘3得到的，又或是说某个数通过乘5得到的。我们可以比较一下这个新的丑数等于究竟是等于第a个丑数乘2, 还是第b个数乘3，还是第c个数乘5，通过比较我们肯定可以知道这个新的丑数到底是哪个数通过乘哪个数得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，下次应该乘2的是第（a+1）个数, 所以a++；如果新的丑数是通过第b个数乘3得到的, 说明此时第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数，此时我们可以说前 b 个数都已经乘过一次3了，下次应该乘3的是第（b+1）个数, 所以 b++；同理，如果这个这个新的丑数是通过第c个数乘5得到的, 那么c++;

但是注意，如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5，说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b都应该加一，因为此时第a个数已经通过乘2得到了一个新的丑数，第b个数已经通过乘3得到了一个新的丑数, 只不过这两个数相等而已。所以我们给计数器加一的时候不能使用 if else else if，而应该使用if, if, if, 这样才不会把应该加一的计数器漏掉
---引用题解评论

通过已经形成的丑数和2，3，5进行相乘。根据大小判断来判断为第几个。

当当前的nums[i]与相乘的结果相等，那么就可以将指针往前挪一个位置，这样就算是重复的元素，也不会重复进入数组，可以保证不重复
动态规划

class Solution:
    def nthUglyNumber(self, n: int) -> int:

        i2,i3,i5=0,0,0
        if n==1:
            return 1
        nums=[1]
        for i in range(1,n):
            nums.append(min(nums[i2]*2,min(nums[i3]*3,nums[i5]*5)))
            if nums[i]==nums[i2]*2:
                i2+=1
            if nums[i]==nums[i3]*3:
                i3+=1
            if nums[i]==nums[i5]*5:
                i5+=1
        return nums[n-1]

通过小根堆，可以使用heapq.heappop(heap) heapq.heappush(heap,item)
每次将最小的元素出堆，然后通过与[2,3,5]分别相乘，判断是否已在堆中存在，如果不存在则将其入堆，然后循环。

class Solution:
    def nthUglyNumber(self, n: int) -> int:

       heap=[1]
       seen={1}
       for _ in range(n-1):
            item=heapq.heappop(heap)
            for i in [2,3,5]:


                if item*i not in seen:
                    seen.add(item*i)
                    heapq.heappush(heap,item*i)

       return heapq.heappop(heap)