golang刷leetcode 数学（1） 丑数系列

1，丑数

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:


输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:


输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。
说明：

复制

1 是丑数。

输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。

解题思路：

1，只包含给定因子，找出所有因子，看是否包含其他

func isUgly(num int) bool {
    if num<1{
        return false
    }
    for num!=1{
        if num%2==0 {
           num/=2
        }else if num%3==0{
            num/=3
        }else if num%5==0{
            num/=5
        }else{
            return false
        }
    }
    return true
}

复制

2，丑数||

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10

输出: 12

解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。

n 不超过1690。

解题思路：

1，先列出1到5的丑数

2，分别用每个因子，乘已有的丑数，取最小值

3，移动被乘丑数的下标，直到n个

代码实现

func nthUglyNumber(n int) int {
    r:=[]int{ 1, 2, 3, 4, 5}
    if n<=5{
    return r[n-1]
    }
         ptr2:= 2
         ptr3:= 1
         ptr5:= 1
        for i:= 5; i < n; i++ {
            if r[ptr2] * 2 == r[len(r)-1]{
                ptr2++
            } 
            if r[ptr3] * 3 == r[len(r)-1]{
               ptr3++
            }
            if r[ptr5] * 5 == r[len(r)-1]{
               ptr5++
            } 
             now1:= r[ptr2] * 2
            now2:= r[ptr3] * 3
            now3 := r[ptr5] * 5;
            r=append(r,min(now1,now2,now3))
        }
        return r[n-1]
}

func min(a,b,c int)int{
    if a<=b && a<=c{
        return a
    }

    if b<=a&&b<=c{
        return b
    }
    return c
}

复制

3，丑数 III

请你帮忙设计一个程序，用来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数。

示例 1：


输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：


输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
示例 3：


输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
示例 4：


输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984
 

复制

提示：

1 <= n, a, b, c <= 10^9

1 <= a * b * c <= 10^18

本题结果在 [1, 2 * 10^9] 的范围内

解题思路：

1，注意，这里的丑数定义和前面不一样，前面是只有指定因子，这里是包含

2，求包含指定因子数的个数有下列公式

f(a)+f(b)+f(c)-f(ab)-f(ac)-f(bc)+f(abc)

其中

A，f(a) 含因子a的个数

B，f(ab)含ab最小公倍数的个数

C,f(abc) 含abc最小公倍数的个数

3，最小公倍数可以用最大公约数来求

4，最大公约数用高斯法

5，用二分法查找

代码实现

func nthUglyNumber(n int, a int, b int, c int) int {
       ab := MCM(a, b)
       ac := MCM(a, c)
       bc := MCM(b, c)
       abc := MCM(ab, c)
       l:=min(a,min(b,c))
       r:= int(2 * 10e9)
        for l < r{
            m:=l + (r - l) / 2
            count:= m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;
            if count < n{
                l = m + 1
            } else {
                r = m
            }
        }
        return l 
}

func MCM( a,  b int)int {
        return (a * b) / gcd(a, b)
    }

func gcd( a, b int)int{
        for b!=0{
        aliquant:=a%b
            a=b
            b=aliquant
        }
        return  a
}

func min (a,b int)int{
    if a<b{
        return a
    }
    return b
}

复制

4，超级丑数

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12, primes = [2,7,13,19]
输出: 32 
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

复制

说明:

1 是任何给定 primes 的超级丑数。

给定 primes 中的数字以升序排列。

0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。

第 n 个超级丑数确保在 32 位有符整数范围内。

解题思路：

1，超级丑数均为结果集合中的每个数和素数集合中的每个数相乘的来。

2，首先维护一个数组记录当前素数集合中的第i个数下一次需要乘结果集合中哪个下标对应的数

3，再维护一个数组记录第i个素数当前未加入到结果集合中的最小的次数

4，遍历n-1次，每次找到所有素数集合中乘上结果集合中的数对应的最小的数，加入结果集合。

5，同时，更新该加入结果集合的素数对应的应乘结果集合的下标后移一位

代码实现

func nthSuperUglyNumber(n int, primes []int) int {

       tmp:=[]int{1}
       flag:=make([]int,len(primes))
       f2:=make([]int,len(primes))
        for i:=0;i<len(primes);i++{
            f2[i]=1
        }
        for i:= 1; i < n; i++{
             minn:=int(^uint(0) >> 1)
            for j:= 0; j < len(primes); j++{
                if tmp[i - 1] == f2[j]{
                   f2[j] = primes[j] * tmp[flag[j]]
                   flag[j]++
                } 
                minn = min(minn, f2[j]);
            }
            tmp=append(tmp,minn)
        }
        
        return tmp[n - 1]
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

复制