首页 > 其他分享 >丑数系列

丑数系列

时间:2022-08-27 22:46:18浏览次数:138  
标签:丑数 curr int res record 系列 primes

264. 丑数 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

问题求解

对于每一个丑数num,都可以扩展到num * 2,num * 3,num * 5三个数字。
可以设置三个指针分别指向当前处理的数字,然后进行比较迭代即可。
快慢指针。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [1]
        i, j, k = 0, 0, 0

        while len(res) < n:
            n1, n2, n3 = res[i] * 2, res[j] * 3, res[k] * 5
            curr = min(n1, n2, n3)
            if n1 == curr: i += 1
            if n2 == curr: j += 1
            if n3 == curr: k += 1
            res.append(curr)
        
        return res[-1]

313. 超级丑数

问题描述

超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 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 <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ,且按 递增顺序 排列

问题求解

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        res = [1]
        ps = [0] * len(primes)

        while len(res) < n:
            record = [primes[i] * res[p] for i, p in enumerate(ps)]
            curr = min(*record) if len(record) > 1 else record[0]
            for i, r in enumerate(record):
                if r == curr:
                    ps[i] += 1
            res.append(curr)

        return res[-1]

标签:丑数,curr,int,res,record,系列,primes
From: https://www.cnblogs.com/hyserendipity/p/16631689.html

相关文章

  • identity4 系列————纯js客户端案例篇[四]
    前言前面已经解释了两个案例了,通信原理其实已经很清楚了,那么纯js客户端是怎么处理的呢?正文直接贴例子哈。https://github.com/IdentityServer/IdentityServer4/tree/ma......
  • 学习ASP.NET Core Blazor编程系列一——综述
    一、NET6概述   .NET6是微软统一.NetCore与.NetFramework两大框架的第二个版本,微软在.NET5中开始进行这两大框架的统一之路。   .NET6将作为长期支持......
  • 关于stm32f10xRB系列的PB5和PB12外设冲突问题
      上周在公司做了一个项目,调试一个mcu,本以为很简单的调试一下裸机驱动,但是调试过程中遇到了一些问题让我觉得比较有意思,记录一下。1、关于stm32的SMBUS功能的介绍  ......
  • 8、开发工具软件 - 软件技术系列文章
        在实际的软件开发和项目管理过程中,都需要很多的工具软件,使用这些软件,能够提高软件人员的工作效率,笔者在总结软件技术的时候,就收集整理了一些软件工具,以便需要的......
  • 7、软件复用 - 软件技术系列文章
        软件复用主要是为了解决在实际的软件开发过程中重复的工作,在其它软件功能相同或相近的时候,直接将代码放过去然后进行下修改即可。这个也是参考的软件定制,比如购......
  • 优先队列-多路归并系列题解
    373.查找和最小的K对数字问题描述给定两个以升序排列的整数数组nums1和nums2 , 以及一个整数k 。定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来......
  • ctfshow 萌新web系列--4
    <html><head><title>ctf.show萌新计划web1</title><metacharset="utf-8"></head><body><?php#包含数据库连接文件include("config.php");#判断get提......
  • Java Servlet 入门: 问题系列:Filter中通过HttpServletRequest.getParts()获取不到上传
    问题:一开始以为Servlet 没有提供对文件读取的相关内容。后来发现,HttpServletRequest中有getParts方法,可以获取上传的文件。再后发,经过反复测试,发现都读不到相关内容。......
  • ctfshow 萌新web系列--3
    <html><head><title>ctf.show萌新计划web1</title><metacharset="utf-8"></head><body><?php#包含数据库连接文件include("config.php");#判断get提......
  • SparkCore系列(四)函数大全
    有了上面三篇的函数,平时开发应该问题不大了。这篇的主要目的是把所有的函数都过一遍,深入RDD的函数RDD函数大全数据准备        val sparkconf = new Spa......