当前位置: 首页 > news >正文

【LeetCode】剑指 Offer(25)

目录

题目:剑指 Offer 49. 丑数 - 力扣(Leetcode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 49. 丑数 - 力扣(Leetcode)

题目的接口:

class Solution {
public:int nthUglyNumber(int n) {}
};

解题思路:

丑数这道题用到一点动态规划的思想,

具体思路如下:

根据题意:

如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数,

那么我们发现,之后的丑数:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

都是前面的丑数乘2、乘3或者乘5 得来的,

那我们的思路就能变成:

从第一个数1开始,让他乘2、乘3、乘5,

第二个数也这样操作,

然后取他们的最小值作为下一个丑数,

以此类推, 

三个指针,分别用来乘2、乘3、乘5,

取得最小值的那个指针指向下一个数,

如果出现两个数相等的情况,

例:

2 * 5 == 5 * 2

那就两个指针都指向下一个数,

防止重复,

最后返回第n个丑数即可。

例:

根据规则:从第一个数1开始,让他乘2、乘3、乘5

一乘二,指针往后走一个:

一乘三,指针往后走一个:

这个时候,二乘二比一乘五更小,

所以这里走的是二乘二:

  

然后是一乘五:

 

 以此类推,就能计算出之后的丑数了。

 下面是代码:

代码:

class Solution {
public:int nthUglyNumber(int n) {//创建n + 1大小的数组vector<int> dp(n + 1);//初始化三指针   int a = 0, b = 0, c = 0;//数组从1开始dp[0] = 1;//循环for(int i = 1; i < n; i++){//让三指针*2 *3 *5 并选出最小值,就是下一个丑数int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;//取最小值dp[i] = min(min(n2, n3), n5);//如果该下标对应的数是下一个丑数,就让指针指向下一个//如果有两个数结果相同,就让那两个指针都指向下一个//防止重复if(n2 == dp[i]){a++;}if(n3 == dp[i]){b++;}if(n5 == dp[i]){c++;}}//最后返回第n个丑数return dp[n - 1];}
};

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

http://www.lryc.cn/news/39882.html

相关文章:

  • 【数据结构】链表OJ
  • 电子工程师必须掌握的硬件测试仪器,你确定你都掌握了?
  • 高速PCB设计指南系列(四)
  • ODrive入门配置
  • 快速测试两台服务器间的网速(ChatGPT回复)
  • 彻底搞懂nodejs事件循环
  • Linux基础命令大全(下)
  • Matplotlib从入门到精通05-样式色彩秀芳华
  • < CSS小技巧:那些不常用,却很惊艳的CSS属性 >
  • GPT-4 重磅发布,用户直呼:强得离谱
  • 【JavaSE】知识点总结(3)
  • MySQL基础(三)聚合函数、子查询
  • 深度学习数据集处理基础内容——xml和json文件详解
  • 蓝桥杯基础技能训练
  • 【Kubernetes】第二十八篇 - 实现自动构建部署
  • 蓝桥杯刷题第十天
  • 网络安全缓冲区溢出与僵尸网络答题分析
  • 机器学习:逻辑回归模型算法原理(附案例实战)
  • IO流之 File 类和字节流
  • 【华为机试真题 Python实现】2023年1、2月高频机试题
  • 【拳打蓝桥杯】最基础的数组你真的掌握了吗?
  • 断崖式难度的春招,可以get这些点
  • 一年经验年初被裁面试1月有余无果,还遭前阿里面试官狂问八股,人麻了
  • 我从功能测试到python接口自动化测试涨到22k,谁知道我经历了什么......
  • SDG,ADAM,LookAhead,Lion等优化器的对比介绍
  • 【项目实现典型案例】12.数据库数据类型不一致导致查询慢
  • 【大数据开发】报错汇总
  • HTTPS的加密原理(工作机制)
  • Git仓库迁移
  • 用CHATGPT生成C++面试题及答案