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