• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

剑指offer刷题记——丑数

C++ root 2年前 (2019-03-29) 515次浏览 已收录 0个评论

丑数

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

分析

本体难度偏中等,难点集中在如何建立丑数序列。所以首先要明确丑数的实际含义,它和质数的本质区别在于一个数字能被分解的最小因子是2,3,5就符合了丑数的定义,比如8这个数字可以用2^3来表示,所以8就是丑数。所以从这个定义出发,所有的丑数实际上是用1累成2, 3,5得到的。所以我们声明一个向量(栈也是可以得),初始的丑数实际上是1,其余剩下的所有丑数使用1和2、3、5开始进行累乘获得,但是如果直接这样操作一定会出现大量重复的数字。所以下一步是如何进行添加新丑数且避免不重复的丑数。所以首先声明一个向量,并将1作为第一个数据存入向量,之后的推荐解决办法如下:
1. 同时使用三个指向该向量的指针ptr2,ptr3,ptr5,初始状态同时指向向量的第一个位置;
2. ptr2指针指向的数据只与2进行乘法运算,同理,另外两个指针只和3或5进行乘法运算,取出最小的乘积结果,第一次的乘积结果分别为2、3、5,经过比较,2最小,将2存入向量;
3. 获得该次最小乘积结果的指针向后移,第一次运算的结果中,2是由ptr2指针的乘法运算获得,ptr2向后移,即指向向量中的第二个位置。
4. 重复2,3两个步骤,直到向量中存储了足够数量以满足题目输入的N。
python的解决办法和C++一样,这道题就不再翻译一遍了(其实就是懒)

使用到的知识点

C++

序列构建

Python

暴力法,没什么知识点

题解

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<7) 
            return index;
        int NewUglyNum = 1;
        int ptr2=0,ptr3=0,ptr5 = 0; //三个队列的指针
        vector<int> uglynumbers;
        uglynumbers.push_back(NewUglyNum);
        while(uglynumbers.size() < index){
            //选出三个队列头最小的数
            NewUglyNum = min(uglynumbers[ptr2] * 2, min(uglynumbers[ptr3] * 3, uglynumbers[ptr5] * 5));
            //这三个if有可能进入一个或者多个,进入多个是三个队列头最小的数有多个的情况
            if(uglynumbers[ptr2] * 2 == NewUglyNum) ptr2++;
            if(uglynumbers[ptr3] * 3 == NewUglyNum) ptr3++;
            if(uglynumbers[ptr5] * 5 == NewUglyNum) ptr5++;
            uglynumbers.push_back(NewUglyNum);
        }
            return NewUglyNum;
    }
};

XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:剑指offer刷题记——丑数
喜欢 (0)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址