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/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
