专栏首页AI那点小事剑指offer——丑数

剑指offer——丑数

概述

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


C++ AC代码

#include <iostream>
#include <cmath>
#include <vector> 
using namespace std;

class Solution {
    public:
        int GetUglyNumber_Solution(int index) {
            if(index < 7){
                return index;
            }
            vector<int> ans(index);
            ans[0] = 1;
            int t2 = 0,t3 = 0,t5 = 0;
            for(int i = 1 ; i < index ; i++){
                ans[i] = min(ans[t2]*2,min(ans[t3]*3,ans[t5]*5));
                if(ans[t2]*2 == ans[i]){
                    t2++;
                }
                if(ans[t3]*3 == ans[i]){
                    t3++;
                }
                if(ans[t5]*5 == ans[i]){
                    t5++;
                }
            }
            return ans[index-1];
        }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CCF考试——201312-3 最大的矩形

      在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别...

    AI那点小事
  • 【剑指offer】31.整数中1出现的次数

    求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共...

    AI那点小事
  • 剑指offer——二叉搜索树的第k个结点

    题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

    AI那点小事
  • Gym 100952H&&2015 HIAST Collegiate Programming Contest H. Special Palindrome【dp预处理+矩阵快速幂/打表解法】

    H. Special Palindrome time limit per test:1 second memory limit per test:64 mega...

    Angel_Kitty
  • NYOJ----次方求模

    次方求模 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 求a的b次方对c取余的值 输入第一行输入一个整数n表示测试数据的组数...

    Gxjun
  • 勾股数组

          一般地,若三角形三边长a,b,c都是正整数,且满足a,b的平方和等于c的平方,那么数组(a,b,c)称为勾股数组。勾股数组是人们为了解出满足勾...

    Ch_Zaqdt
  • 开始使用Octave

    mwangblog
  • 南昌大学航天杯第二届程序设计竞赛校赛网络同步赛 水题

    链接:https://www.nowcoder.com/acm/contest/122/C 来源:牛客网

    用户2965768
  • 【Gym 100947C】Rotate It !!

    饶文津
  • LeetCode 273. Integer to English Words

    ShenduCC

扫码关注云+社区

领取腾讯云代金券