【LeetCode】剑指 Offer(25)

这篇具有很好参考价值的文章主要介绍了【LeetCode】剑指 Offer(25)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


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

【LeetCode】剑指 Offer(25)

题目的接口:

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个丑数即可。

例:

【LeetCode】剑指 Offer(25)

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

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

【LeetCode】剑指 Offer(25)

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

【LeetCode】剑指 Offer(25)

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

所以这里走的是二乘二:

【LeetCode】剑指 Offer(25)  

然后是一乘五:

 【LeetCode】剑指 Offer(25)

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

 下面是代码:

代码:

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];
    }
};

过啦!!!

【LeetCode】剑指 Offer(25)

写在最后:

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

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

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

之后我还会输出更多高质量内容,欢迎收看。文章来源地址https://www.toymoban.com/news/detail-405752.html

到了这里,关于【LeetCode】剑指 Offer(25)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】丑数题目合辑

    思路 首先,丑数必须是 正整数 ,因此对于 n1 都可以直接返回 false; 对于 n = 1 ,如果 n 能够被 2/3/5 整除,说明它们是丑数。 代码 思路 要得到第 n 个丑数,可以使用 最小堆 实现。 初始化堆为空,首先将最小的丑数 1 加入。每次取出堆顶元素 x ,则 x 是堆中最小的丑数,

    2024年02月13日
    浏览(47)
  • 【剑指offer刷题记录 java版】数组双指针 之 其它题目

    本系列文章记录labuladong的算法小抄中剑指offer题目 题目链接:https://leetcode.cn/problems/XltzEq/ 题目链接:https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/ 题目链接:https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/ 题目链接:https://leetcode.cn/problems/he-wei-sde-

    2024年02月11日
    浏览(48)
  • 【LeetCode】剑指 Offer(21)

    目录 题目:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 40. 最小的k个数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题,我的思路是直接排序, 然后返回中间

    2023年04月10日
    浏览(65)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(51)
  • 【LeetCode】剑指 Offer(26)

    目录 题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这一道题,我的思路是用双指针暴力求解, 但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完, 看了大佬的思路,用的是归并排序,(如果不

    2023年04月11日
    浏览(42)
  • 【LeetCode】剑指 Offer(27)

    目录 题目:剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 那么这道题呢, 如果只是作为一道题,或者说笔试题, 我们当然是二话不说直接暴力拿下, 来看代码: 是的,就是这么简单,三行代码暴力拿下

    2023年04月13日
    浏览(44)
  • 【LeetCode】剑指 Offer <二刷>(1)

    目录 前言: 题目:剑指 Offer 03. 数组中重复的数字 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 刚学 golang 半个多月,看了一堆的文档啊,框架啊,许许多多的东西,学到了很多,但是代码没有怎么上手写,所以我就决定用 golang 二刷剑指 Offe

    2024年02月09日
    浏览(41)
  • 【LeetCode】剑指 Offer <二刷>(5)

    目录 题目:剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 11. 旋转数组的最小数字 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题乍一看好像没什么思路,但是我们不妨把题

    2024年02月09日
    浏览(35)
  • 【LeetCode】剑指 Offer <二刷>(4)

    目录 题目:剑指 Offer 09. 用两个栈实现队列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题我用 C++ 写的时候是比较简单顺手的,用 STL 可以

    2024年02月10日
    浏览(42)
  • 【LeetCode】剑指 Offer <二刷>(3)

    目录 题目:剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 07. 重建二叉树 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题我读完之后想到了两种思路,1、直接从后往前去链表

    2024年02月10日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包