Golang每日一练(leetDay0106) 超级丑数、右侧小于当前元素的个数

简介: Golang每日一练(leetDay0106) 超级丑数、右侧小于当前元素的个数

313. 超级丑数 Super Ugly Number

超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ,返回第 n超级丑数

题目数据保证第 n超级丑数32-bit 带符号整数范围内。

示例 1:

输入: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] 。

示例 2:

输入:n = 1, primes = [2,3,5]

输出:1

解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。


提示:

  • 1 <= n <= 10^6
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • 题目数据 保证primes[i] 是一个质数
  • primes 中的所有值都 互不相同 ,且按 递增顺序 排列

代码:动态规划

package main
import "fmt"
func nthSuperUglyNumber(n int, primes []int) int {
  dp := make([]int, n)
  dp[0] = 1
  idx := make([]int, len(primes))
  min := func(x, y int) int {
    if x < y {
      return x
    }
    return y
  }
  for i := 1; i < n; i++ {
    dp[i] = 1<<31 - 1
    for j := 0; j < len(primes); j++ {
      tmp := dp[idx[j]] * primes[j]
      dp[i] = min(dp[i], tmp)
    }
    for j := 0; j < len(primes); j++ {
      if dp[i]%primes[j] == 0 {
        idx[j]++
      }
    }
  }
  return dp[n-1]
}
func main() {
  n, primes := 12, []int{2, 7, 13, 19}
  fmt.Println(nthSuperUglyNumber(n, primes))
  n, primes = 1, []int{2, 3, 5}
  fmt.Println(nthSuperUglyNumber(n, primes))
}

输出:

32

1

根据丑数定义来暴力枚举:

```golang
func nthSuperUglyNumber(n int, primes []int) int {
    count := 0
    isSuperUglyNumber := func(num int, primes []int) bool {
        for _, p := range primes {
            for num%p == 0 {
                num /= p
            }
        }
        return num == 1
    }
    for num := 1; num < 1<<31; num++ {
        if isSuperUglyNumber(num, primes) {
            count++
            if count == n {
                return num
            }
        }
    }
    return -1
}
```

315. 计算右侧小于当前元素的个数 Count-of-smaller-numbers-after-self

给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1:

输入:nums = [5,2,6,1]

输出:[2,1,1,0]

解释:

5 的右侧有 2 个更小的元素 (2 和 1)

2 的右侧仅有 1 个更小的元素 (1)

6 的右侧有 1 个更小的元素 (1)

1 的右侧有 0 个更小的元素


示例 2:

输入:nums = [-1]

输出:[0]


示例 3:

输入:nums = [-1,-1]

输出:[0,0]


提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

代码:归并排序

package main
import "fmt"
func countSmaller(nums []int) []int {
  n := len(nums)
  counts := make([]int, n)
  pairs := make([]*Pair, n)
  for i := 0; i < n; i++ {
    pairs[i] = &Pair{nums[i], i}
  }
  mergeSort(pairs, 0, n-1, counts)
  return counts
}
type Pair struct {
  num, index int
}
func mergeSort(pairs []*Pair, left, right int, counts []int) {
  if left < right {
    mid := left + (right-left)/2
    mergeSort(pairs, left, mid, counts)
    mergeSort(pairs, mid+1, right, counts)
    merge(pairs, left, mid, right, counts)
  }
}
func merge(pairs []*Pair, left, mid, right int, counts []int) {
  tmp := make([]*Pair, right-left+1)
  i, j, k := left, mid+1, 0
  for i <= mid && j <= right {
    if pairs[i].num <= pairs[j].num {
      tmp[k] = pairs[j]
      k++
      j++
    } else {
      tmp[k] = pairs[i]
      counts[pairs[i].index] += (right - j + 1)
      k++
      i++
    }
  }
  for i <= mid {
    tmp[k] = pairs[i]
    k++
    i++
  }
  for j <= right {
    tmp[k] = pairs[j]
    k++
    j++
  }
  for i, pair := range tmp {
    pairs[left+i] = pair
  }
}
func main() {
  nums := []int{5, 2, 6, 1}
  fmt.Println(countSmaller(nums))
  nums = []int{-1}
  fmt.Println(countSmaller(nums))
  nums = []int{-1, -1}
  fmt.Println(countSmaller(nums))
}

输出:

[2 1 1 0]

[0]

[0 0]

暴力枚举:

```golang
func countSmaller(nums []int) []int {
    n := len(nums)
    counts := make([]int, n)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[i] {
                counts[i]++
            }
        }
    }
    return counts
}
```

🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页: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)暂停更


目录
相关文章
|
6月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
93 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
6月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
65 0
Linux 终端命令之文件浏览(2) more
|
6月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
61 0
Linux 终端操作命令(2)内部命令
|
6月前
|
C++ 算法 存储
力扣 C++|一题多解之动态规划专题(2)
力扣 C++|一题多解之动态规划专题(2)
62 0
力扣 C++|一题多解之动态规划专题(2)
|
6月前
|
Python 索引
Python Numpy入门基础(一)创建数组
Python Numpy入门基础(一)创建数组
71 0
Python Numpy入门基础(一)创建数组
|
2月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
114 4
Golang语言之管道channel快速入门篇
|
2月前
|
Go
Golang语言文件操作快速入门篇
这篇文章是关于Go语言文件操作快速入门的教程,涵盖了文件的读取、写入、复制操作以及使用标准库中的ioutil、bufio、os等包进行文件操作的详细案例。
67 4
Golang语言文件操作快速入门篇
|
2月前
|
Go
Golang语言之gRPC程序设计示例
这篇文章是关于Golang语言使用gRPC进行程序设计的详细教程,涵盖了RPC协议的介绍、gRPC环境的搭建、Protocol Buffers的使用、gRPC服务的编写和通信示例。
104 3
Golang语言之gRPC程序设计示例
|
2月前
|
安全 Go
Golang语言goroutine协程并发安全及锁机制
这篇文章是关于Go语言中多协程操作同一数据问题、互斥锁Mutex和读写互斥锁RWMutex的详细介绍及使用案例,涵盖了如何使用这些同步原语来解决并发访问共享资源时的数据安全问题。
86 4
|
2月前
|
Go 调度
Golang语言goroutine协程篇
这篇文章是关于Go语言goroutine协程的详细教程,涵盖了并发编程的常见术语、goroutine的创建和调度、使用sync.WaitGroup控制协程退出以及如何通过GOMAXPROCS设置程序并发时占用的CPU逻辑核心数。
52 4
Golang语言goroutine协程篇