目录

263. 丑数 Ugly Number I  ?

264. 丑数 Ugly Number II  ??

? 每日一练刷题专栏 ?

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

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/