文档章节

【剑指offer】丑数,C++实现

o
 osc_vpogdtu8
发布于 07/01 08:27
字数 725
阅读 16
收藏 0

精选30+云产品,助力企业轻松上云!>>>

原创博文,转载请注明出处!
本题牛客网地址

博客文章索引地址

博客文章中代码的github地址

1. 题目

image

2. 思路

      空间换时间的方法。由于题目要求按序查找丑数,可以采用辅助容器vector按序存储丑数,返回指定位置丑数的策略。用辅助容器vector按序存储丑数的关键在于怎么按序计算丑数。按序计算丑数的方法:设辅助变量t2为一个丑数在vector中的索引,t2位置之前的丑数*2之后小于等于最大丑数,t2位置及t2位置之后的丑数*2后大于最大丑数。设辅助变量t3为一个丑数在vector中的索引,t3位置之前的丑数*3之后小于等于最大丑数,t3位置及t3位置之后的丑数*3后大于最大丑数。设辅助变量t5为一个丑数在vector中的索引,t5位置之前的丑数*5之后小于等于最大丑数,t5位置及t5位置之后的丑数*5后大于最大丑数。min(t2位置的丑数*2,t3位置的丑数*3,t5位置的丑数*5)即为最大丑数p后面的丑数q。

      举例:

image

思路总结如下:

  • 特殊输入
    • 由于1,2,3,4,5,6都是丑数,那么如果index<7时,直接输出index即
  • 辅助空间
    • vector:用vector存储按序生成的丑
  • 辅助变量
    • t2:t2位置之前的丑数*2之后 ≤ 最大丑数,t2位置的丑数*2之后 > 最大丑数
    • t3:t3位置之前的丑数*3之后 ≤ 最大丑数,t3位置的丑数*3之后 > 最大丑数
    • t5:t5位置之前的丑数*5之后 ≤ 最大丑数,t5位置的丑数*5之后 > 最大丑
  • 按序计算丑数
    • 按序计算最大丑数
      • 最大丑数 = min(vec[t2]*2,vec[t3]*3,vec[t5]*5)
    • 更新三个辅助变量
      • 当vec[t2]*2 == 最大丑数时,证明最大丑数 = t2位置的丑数 * 2,不满足t2的定义。
      • 当vec[t3]*3 == 最大丑数时,证明最大丑数 = t3位置的丑数 * 3,不满足t3的定义。
      • 当vec[t5]*5 == 最大丑数时,证明最大丑数 = t5位置的丑数 * 5,不满足t5的定义。


3. 代码

  1 class Solution {
  2 public:
  3     int GetUglyNumber_Solution(int index) {
  4 
  5         // 特殊输入
  6         if(index<7) return index;
  7 
  8         // 辅助容器
  9         vector<int> res(index);
 10         for(int i = 0;i<6;i++)
 11             res[i] = i+1;
 12 
 13         // 辅助变量
 14         int t2=3;
 15         int t3=2;
 16         int t5=1;
 17 
 18         // 按序计算丑数
 19         for(int i =6;i<index;i++)
 20         {
 21             res[i] = min(res[t2]*2,min(res[t3]*3,res[t5]*5));
 22 
 23             if(res[i] == res[t2] * 2 ) t2++;
 24             if(res[i] == res[t3] * 3 ) t3++;
 25             if(res[i] == res[t5] * 5 ) t5++;
 26         }
 27         return res[index-1];
 28     }
 29 };

下一篇: java多态
o
粉丝 0
博文 60
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
博文目录

为了方便阅读,梳理了一个博文目录。博文里面多数是近两年存储在为知笔记里面的笔记,包括《剑指offer》、《python基础》、《python库》、《Machine Learning》、《Deep Learning》、《数据挖...

osc_6zu0q9s3
2018/03/03
4
0
LeetCode 295. Find Median from Data Stream数据流的中位数 (C++/Java)

题目: Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For e......

osc_hwpd2zko
01/06
3
0
剑指offer【40~49】

题目链接: 剑指offer 40-49 目录: 40. 最小的 K 个数 41.1 数据流中的中位数 41.2 字符流中第一个不重复的字符 42. 连续子数组的最大和 43. 从 1 到 n 整数中 1 出现的次数 44. 数字序列中...

牛奶芝麻
2019/12/19
0
0
读书笔记| 剑指offer

date: 2016-06-02 14:00 剑指 offer 何海涛blog: http://zhedahht.blog.163.com/ 源码: http://download.csdn.net/download/cadcisdhht/3809923 读书笔记 程序的鲁棒性很重要, 要注意 边界条......

daydaygo
2018/11/08
0
0
服务器开发必读书籍

转 一、算法基础系列 数据结构基础(C语言版)》朱仲涛 译 《剑指Offer》 《编程之美》 《编程珠玑》 《CareerCup-Top 150 Questions 4th》 《[算法导论].(美国)Cormen.扫描版》 二、C/C++面试...

osc_k5dg06i6
2019/05/24
4
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka如何在千万级别时优化JVM GC问题?

大家都知道Kafka是一个高吞吐的消息队列,是大数据场景首选的消息队列,这种场景就意味着发送单位时间消息的量会特别的大,那既然如此巨大的数据量,kafka是如何支撑起如此庞大的数据量的分发...

hummerstudio
06/18
6
0
我打赌!90%程序员都破解不了这个粽子,不信你试!

放假了 各位读者朋友们,马上就是端午小长假啦,开心激动有木有? 新的故事文章还在创作中,写了初稿感觉不太满意又推倒重来。其实写故事还是挺难的,读者可能第一次第二次有新鲜感,写多了就...

轩辕之风
06/24
20
0
如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

前言 “删库跑路”是程序员经常谈起的话题,今天,我就要教大家如何删!库!跑!路! 开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解...

后端技术漫谈
01/14
22
0
PHP设计模式之代理模式

PHP设计模式之代理模式 代理人这个职业在中国有另外一个称呼,房产经济人、保险经济人,其实这个职业在国外都是叫做房产代理或者保险代理。顾名思义,就是由他们来帮我们处理这些对我们大部分...

硬核项目经理
2019/09/23
11
0
Redis的复制模式

Redis的复制功能分为同步(sync)和命令传播(command propagate)两个操作。 同步 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。 1. 旧版本的执行步骤 从服务器...

osc_s9cni3go
41分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部