目录
263. 丑数 Ugly Number I
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。 示例 3：
输入：n = 14 输出：false 解释：14 不是丑数，因为它包含了另外一个质因数 7 。
提示：
-2^31 <= n <= 2^31 - 1
代码：
package main
import "fmt"
func isUgly(n int) bool {
if n <= 0 {
return false
}
for _, i := range []int{2, 3, 5} {
for n%i == 0 {
n /= i
}
}
return n == 1
}
func main() {
fmt.Println(isUgly(6))
fmt.Println(isUgly(1))
fmt.Println(isUgly(14))
for i := 1; i < 21; i++ {
if isUgly(i) {
fmt.Print(i, " ")
}
}
fmt.Println()
}
递归写法：
package main
import "fmt"
func isUgly(n int) bool {
if n <= 0 {
return false
} else if n == 1 {
return true
} else if n%2 == 0 {
return isUgly(n / 2)
} else if n%3 == 0 {
return isUgly(n / 3)
} else if n%5 == 0 {
return isUgly(n / 5)
} else {
return false
}
}
func main() {
fmt.Println(isUgly(6))
fmt.Println(isUgly(1))
fmt.Println(isUgly(14))
for i := 1; i <= 20; i++ {
if isUgly(i) {
fmt.Print(i, " ")
}
}
}
输出：
true
true
false
1 2 3 4 5 6 8 9 10 12 15 16 18 20
264. 丑数 Ugly Number II
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1 输出：1 解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
代码：
package main
import "fmt"
func nthUglyNumber(n int) int {
nums := []int{1}
p2, p3, p5 := 0, 0, 0
for i := 1; i < n; i++ {
tmp := min(nums[p2]*2, nums[p3]*3, nums[p5]*5)
nums = append(nums, tmp)
if nums[i] == nums[p2]*2 {
p2++
}
if nums[i] == nums[p3]*3 {
p3++
}
if nums[i] == nums[p5]*5 {
p5++
}
}
return nums[n-1]
}
func min(a, b, c int) int {
if a < b {
if a < c {
return a
}
} else if b < c {
return b
}
return c
}
func main() {
fmt.Println(nthUglyNumber(10))
fmt.Println(nthUglyNumber(1))
for i := 1; i <= 14; i++ {
fmt.Print(nthUglyNumber(i), " ")
}
fmt.Println()
}
调用上题函数：
package main
import "fmt"
func isUgly(n int) bool {
if n <= 0 {
return false
}
for _, i := range []int{2, 3, 5} {
for n%i == 0 {
n /= i
}
}
return n == 1
}
func nthUglyNumber(n int) int {
count := 0
i := 1
for count < n {
if isUgly(i) {
count++
}
if count == n {
return i
}
i++
}
return -1
}
func main() {
fmt.Println(nthUglyNumber(10))
fmt.Println(nthUglyNumber(1))
for i := 1; i <= 14; i++ {
fmt.Print(nthUglyNumber(i), " ")
}
fmt.Println()
}
输出：
12
1
1 2 3 4 5 6 8 9 10 12 15 16 18 20
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/