IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 冉宝的每日一题--8月9日--超级丑数:最小堆+ 动态规划 -> 正文阅读

[数据结构与算法]冉宝的每日一题--8月9日--超级丑数:最小堆+ 动态规划

刚刚在小红书上研究,怎么做 擂椒茄子松花蛋, 诶,实在是太想吃了。
那么我们就啊开始做每日一题吧,做完就可以睡觉啦!

每日一题: 313.超级丑数

题目描述:

https://leetcode-cn.com/problems/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 <= 106
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ,且按 递增顺序 排列

思路

用时: 11:25 -
思路: 感觉是一个二维动态规划的题目。
以第一个例子为例:
第一个丑数肯定是1 ,可以直接return
然后就是对丑数进行排序,然后就是一个循环
比如
[3,13]
? [3,9,13]
所以: [1,13,133,113]
[39,313]
[99,913]
[13*13]
–> 感觉啊,还是一筹莫展
[2,3,5,7]

看n的范围,我就知道我没戏了,看答案吧
然后发现我的思路是对的,就是太菜了不会实现呢

官方题解: 最小堆

要得到从小到大的第n个超级丑数,可以使用最小堆实现。
初始时,堆为空。将最小的超级丑数1加入堆。
每次取出堆顶元素x,x是堆中最小的超级丑数,
对于数组primes的任意质数p,px也是超级丑数,所以将primes的每个质数与x的乘积分别入堆
上述做法会导致堆中出现重复元素,为了避免,可以用哈希集合去重,避免相同元素多次入堆。

在排除重复元素的情况下,第n次从最小堆中取出的元素是第n个超级丑数。

疑问: 其实我不太明白,我怎么知道堆中的元素够了呢?-- 所以生成nm个


from collections import heapq
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
    	seen = {1}
    	heap = [1]	
    	for i in range(n):
    		ugly = heapq.heappop(heap)
    		for prime in primes:
    			nxt = prime * ugly 
    			if nxt not in seen:
    				seen.add(nxt)
    				heapq.heappush(heap,nxt)
    	return ugly

时间复杂度:O(nmlognm),其中n为待求的超级丑数的编号,m是primes数组的长度,要得到第n个超级丑数,需要进行n次循环,每次循环要从最小堆中取出一个元素,以及最小堆中加入最多m个元素,因此每次循环的时间复杂度: O(lognm + mlognm) = O(mlognm),所以总的时间复杂度为:O(nmlognm)。
空间复杂度: O(mn),其中n为待求的超级丑数的编号,m是primes数组的长度.空间复杂度取决于最小堆和哈希集合的大小,最小堆和哈希集合的大小都不会超过nm。

官方题解:动态规划

方法一使用最小堆,会预先存储比较多的超级丑数,空间复杂度比较高,维护最小堆的过程也导致时间复杂度比较高,所以使用动态规划进行优化。

定义数组dp,其中dp[i]是第i个超级丑数,第n个超级丑数为dp[n]

最小的超级丑数是1,dp[1] =1

如何得到其余的超级丑数呢?创建和数组primes登场的数组 pointers,表示下一个超级丑数是当前指针指向的超级丑数乘以对应的质因数。初始时,数组 pointers的元素都是1.

2 ≤ i ≤ 2 \leq i \leq 2i 时,令 d p [ i ] = m i n 0 ≤ j < m d p [ p o i n t e r [ j ] ] x p r i m e s [ j ] dp[i] = min_{0 \leq j < m}{dp[pointer[j]] x primes[j]} dp[i]=min0j<m?dp[pointer[j]]xprimes[j]
然后比较dp[i] 和 dp[pointer[j] x primes[j] 是否相等,相等 pointer[j] +1 。

时间复杂度:O(mn),其中n为待求的超级丑数的编号,m是primes数组的长度,需要计算数组dp个元素,每个元素的计算时间需要O(m)
空间复杂度:O(m+n),其中n为待求的超级丑数的编号,m是primes数组的长度,需要创建数组dp,和数组pointers,空间为O(n)和O(m)。

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        if n == 1:
            return 1 
        dp = [0 for i in range(n+1)] 
        dp[1] = 1
        pointers = [1 for prime in primes]
        m = len(primes)
        for i in range(2,n+1):
            new_num = min(p1*dp[p2] for p1,p2 in zip(primes,pointers))
            for j in range(m):
                if primes[j] * dp[pointers[j]] == new_num:
                    pointers[j] += 1
            dp[i] = new_num
        return int(dp[-1])

– 注意index从1开始。

睡觉啦,今天睡觉前一定不玩手机好好睡觉,明天早上吃老干妈炒面~

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-10 13:41:03  更:2021-08-10 13:41:08 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 18:41:55-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码