代码编织梦想

【剑指offer-C++】JZ49:丑数

题目描述

描述:把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围:0≤n≤2000。

要求:空间复杂度 O(n) , 时间复杂度 O(n)。

输入:7
返回值:8

解题思路

丑数:最直观的想法是,暴力质因数分解,由于此处质因子只有2、3、5,故与原始质因数分解写法有些许不同。首先编写isUgly函数用于判断数n是否为丑数,由于1、2、3、4、5、6均是丑数,故若index小于等于6,则直接返回index即可,反之记录当前丑数数量num为6,再从7开始遍历,如果当前数是丑数,则对应丑数数量num加一,再判断丑数数量num是否等于给定个数index,如果是则记录结果并返回。(超时)

//判断是否为丑数 与原始的质因数分解不同
bool isUgly(int n)
{
   while(n%2==0) n/=2;
   while(n%3==0) n/=3;
   while(n%5==0) n/=5;
   return n==1;
}
int GetUglyNumber_Solution(int index) 
{
   // 1 2 3 4 5 6均是丑数
   if(index<=6)
      return index;
   //记录第一个丑数
   int num=6; 
   //记录对应结果
   int result;
   for(int i=7;;i++)
   {
       //如果是丑数则丑数数量加一
       if(isUgly(i))
         num++;
       //如果数量等于待求解的则记录结果
       if(num==index)
       {
           result=i;
           break;
       }
   }
   return result;
}

优化:上述方法很明显超时,故我们需要找出方法对其进行优化。由于质因子只有2、3、5的为丑数,且所需的n个丑数是按从小到大的顺序进行排列的,假设我们知道前n-1个丑数,那么我们只需将前n-1个丑数每一个分别乘以2、3、5即可得到新的丑数,然后从中检查出与前n-1个丑数不重复的且最小的丑数即可得到第n个丑数。但是这样做法下的时间复杂度仍然很高,所以我们继续想办法优化。根据规律可以知道,第一个丑数为1,将其分别乘以2、3、5,然后取最小的2,由于2是由1乘以2得到的,所以下一个因为乘以2得到的丑数必然是根据2得到的,这时我们就可以根据此单调性规律来设置三指针。具体做法如下:使用res[i]表示第i个丑数,其中第一个丑数是1,分别使用指针p2、p3、p5表示下一个丑数可以根据res[p2]*2、res[p3]*3、res[p5]*5得到,首先根据三指针得到最小的丑数,然后判断该丑数是由哪一个得到的,并将对应的指针后移,当数组长度小于index时一直执行直至相等,最后返回res最后一个元素即可。

int GetUglyNumber_Solution(int index) 
{
    // 1 2 3 4 5 6均是丑数
    if(index<=6)
       return index;
    //用于记录丑数
    vector<int> res;
    //用于记录最小值
    int minx;
    //第一个丑数为1
    res.push_back(1);
    //三指针 分别标记下一个丑数可以根据 res[i]*2 res[j]*3 res[k]*5得到
    int p2=0,p3=0,p5=0;
    //当数组长度小于index一直执行直至相等
    while(res.size()<index)
    {
        //取最小值
        minx=min({res[p2]*2,res[p3]*3,res[p5]*5});
        res.push_back(minx);
        if(minx==res[p2]*2)
           p2++;
        if(minx==res[p3]*3)
           p3++;
        if(minx==res[p5]*5)
           p5++;
    }
    return res[res.size()-1];
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43779149/article/details/129824200

剑指Offer - JZ49 丑数-爱代码爱编程

描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。 数据范围:0 ≤ n ≤ 2000 要求:空间复杂度 O(n), 时间复杂度 O(n)O 视频 代码 class Solution { public:

剑指offer--JZ3 数组中重复的数字-爱代码爱编程

链接:数组中重复的数字_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目,配有官方题解,在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524?tpId=265&

【剑指offer-c++】jz14:剪绳子-爱代码爱编程

【剑指offer】JZ14:剪绳子 题目描述解题思路 题目描述 描述:给你一根长度为 n 的绳子,请把绳子剪成整数长的 m 段( m 、 n 都是整数, n > 1 并且 m > 1 , m

【剑指offer-c++】jz17:打印从1到最大的n位数-爱代码爱编程

【剑指offer】JZ17:打印从1到最大的n位数 题目描述解题思路 题目描述 描述:输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数

【剑指offer-c++】jz22:链表中倒数最后k个结点-爱代码爱编程

【剑指offer-C++】JZ22:链表中倒数最后k个结点 题目描述解题思路 题目描述 描述:输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。如果该链表长度小于k,请

【剑指offer-c++】jz23:链表中环的入口结点-爱代码爱编程

【剑指offer-C++】JZ23:链表中环的入口结点 题目描述解题思路 题目描述 描述:给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。 数据范围: n≤10000,

【剑指offer-c++】jz26:树的子结构-爱代码爱编程

【剑指offer-C++】JZ26:树的子结构 题目描述解题思路 题目描述 描述:输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构) 假如给定A为{8,8,7,9,2,#

【剑指offer-c++】jz27:二叉树的镜像-爱代码爱编程

【剑指offer-C++】JZ27:二叉树的镜像 题目描述解题思路 题目描述 描述:操作给定的二叉树,将其变换为源二叉树的镜像。 数据范围:二叉树的节点数 0≤n≤1000 , 二叉树每个节点的值 0≤

【剑指offer-c++】jz28:对称的二叉树-爱代码爱编程

【剑指offer-C++】JZ28:对称的二叉树 题目描述解题思路 题目描述 描述:给定一棵二叉树,判断其是否是自身的镜像(即:是否对称) 例如:下面这棵二叉树是对称的: 下面这棵二叉树不对称。

【剑指offer-c++】jz29:顺时针打印矩阵-爱代码爱编程

【剑指offer-C++】JZ29:顺时针打印矩阵 题目描述解题思路 题目描述 描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: [[1,2,3,4

【剑指offer-c++】jz30:包含min函数的栈-爱代码爱编程

【剑指offer-C++】JZ30:包含min函数的栈 题目描述解题思路 题目描述 描述:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 min 函数,输入操作时保证 pop、top 和

【剑指offer-c++】jz37:序列化二叉树-爱代码爱编程

【剑指offer-C++】JZ37:序列化二叉树 题目描述解题思路 题目描述 描述:请实现两个函数,分别用来序列化和反序列化二叉树,不对序列化之后的字符串进行约束,但要求能够根据序列化之后的字符串重新构造

【剑指offer-c++】jz38:字符串的排列-爱代码爱编程

【剑指offer-C++】JZ38:字符串的排列 题目描述解题思路 题目描述 描述:输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则

【剑指offer-c++】jz39:数组中出现次数超过一半的数字-爱代码爱编程

【剑指offer-C++】JZ39:数组中出现次数超过一半的数字 题目描述解题思路 题目描述 描述:给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度

【剑指offer-爱代码爱编程

【剑指offer】JZ15:二进制中1的个数 题目描述解题思路 题目描述 描述:输入一个整数 n ,输出该数32位二进制表示中1的个数。其中负数用补码表示。 数据范围:−231 <=n

【剑指offer-爱代码爱编程

【剑指offer】JZ8 - 二叉树的下一个结点 题目描述解题思路 题目描述 描述:给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同

【剑指offer-爱代码爱编程

【剑指offer】JZ19: 正则表达式匹配 题目描述解题思路 题目描述 描述:请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。 1.模式中的字符’.‘表示任意一个字符。 2.模式中的字

【剑指offer-爱代码爱编程

【剑指offer-C++】JZ35:复杂链表的复制 题目描述解题思路 题目描述 描述:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个

【剑指offer-爱代码爱编程

题目描述 描述:不分行从上往下打印出二叉树的每个节点,同层节点从左至右打印。例如输入{8,6,10,#,#,2,1},如以下图中的示例二叉树,则依次打印8,6,10,2,1(空节点不打印,跳过),请你将打印的结果存放到一个

【剑指offer-爱代码爱编程

【剑指offer-C++】JZ34:二叉树中和为某一值的路径(二) 题目描述解题思路 题目描述 描述:输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为