Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii

简介: Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii

263. 丑数 Ugly Number I

丑数 就是只包含质因数235 的正整数。

给你一个整数 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丑数

丑数 就是只包含质因数 23 和/或 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)暂停更


目录
相关文章
|
7天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
7天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
7天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
43 0
|
7天前
|
存储 算法 程序员
深入理解 C++ 自定义链表中实现迭代器
深入理解 C++ 自定义链表中实现迭代器
61 0
|
7天前
|
存储 算法 Linux
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
67 0
|
7天前
|
存储 算法 编译器
【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用
【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用
21 0
|
7天前
|
存储 缓存 算法
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
60 0
|
7天前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
|
7天前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
31 0
|
7天前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
61 1