golang刷leetcode 数学（1） 丑数系列
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
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
