• 【LeetCode】【剑指offer】【丑数】


    剑指 Offer 49. 丑数 

    我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

    示例:

    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数
    说明:  

    1 是丑数。
    n 不超过1690。

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/chou-shu-lcof
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

     

    我们使用一个result容器来记录我们从小到大的丑数,默认初始值为1,然后用三个指针分别为two,three,five来记录我们应该对哪个数字进行×2或3或5的操作。同时我们挑出其中最小的那个数作为我们当前的丑数结果。

    假设我们当前要求第十个丑数

    我们初始的vector中的第0号元素为1

    我们的two,three,five全部为0

    two

    three

    five

    0

    0

    0

    Vector

    0

    1

    1

     

    然后我们分别用2乘two指针指向的容器中的位置0的数字, 3乘two指针指向的容器中的位置0的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了2,3,5

    从中我们挑选出最小值2,并将其压入vector中,然后将我们two的指针++

    two

    three

    five

    1

    0

    0

    Vector

    0

    1

    1

    2

     然后我们分别用2乘two指针指向的容器中的位置1的数字, 3乘two指针指向的容器中的位置0的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了4,3,5

    从中我们挑选出最小值3,并将其压入vector中,然后将我们three的指针++

    two

    three

    five

    1

    1

    0

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

     然后我们分别用2乘two指针指向的容器中的位置1的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了4,6,5

    从中我们挑选出最小值4,并将其压入vector中,然后将我们two的指针++

    two

    three

    five

    2

    1

    0

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    然后我们分别用2乘two指针指向的容器中的位置2的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了6,6,5

    从中我们挑选出最小值5,并将其压入vector中,然后将我们five的指针++

    two

    three

    five

    2

    1

    1

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    然后我们分别用2乘two指针指向的容器中的位置2的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了6,6,10

    从中我们挑选出最小值6,并将其压入vector中,然后将我们two,three的指针++

    two

    three

    five

    3

    2

    1

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    6

    然后我们分别用2乘two指针指向的容器中的位置3的数字, 3乘two指针指向的容器中的位置2的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了8,9,10

    从中我们挑选出最小值8,并将其压入vector中,然后将我们two的指针++

    two

    three

    five

    4

    2

    1

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    6

    8

    然后我们分别用2乘two指针指向的容器中的位置4的数字, 3乘two指针指向的容器中的位置2的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了10,9,10

    从中我们挑选出最小值9,并将其压入vector中,然后将我们three的指针++

    two

    three

    five

    4

    3

    1

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    6

    8

    9

    然后我们分别用2乘two指针指向的容器中的位置4的数字, 3乘two指针指向的容器中的位置3的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了10,12,10

    从中我们挑选出最小值10,并将其压入vector中,然后将我们two,five的指针++

     

    two

    three

    five

    5

    3

    2

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    6

    8

    9

    10

    然后我们分别用2乘two指针指向的容器中的位置5的数字, 3乘two指针指向的容器中的位置3的数字,5乘two指针指向的容器中的位置2的数字。我们分别得到了12,12,15

    从中我们挑选出最小值12,并将其压入vector中,然后将我们two,three的指针++

    two

    three

    five

    6

    4

    2

    Vector

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1

    2

    3

    4

    5

    6

    8

    9

    10

    12

    这样我们就从n-1也就是我们容器下标9的位置得到了我们的结果12。 

    1. class Solution {
    2. public:
    3. int nthUglyNumber(int n) {
    4. int two=0;
    5. int three=0;
    6. int five=0;
    7. vector<int> result;
    8. result.push_back(1);
    9. for(int i=1;i
    10. {
    11. int n2=result[two]*2;
    12. int n3=result[three]*3;
    13. int n5=result[five]*5;
    14. result.push_back(min(min(n2,n3),n5));
    15. if(result[i]==n2)
    16. {
    17. two++;
    18. }
    19. if(result[i]==n3)
    20. {
    21. three++;
    22. }
    23. if(result[i]==n5)
    24. {
    25. five++;
    26. }
    27. }
    28. return result[n-1];
    29. }
    30. };

  • 相关阅读:
    【jmeter】
    Jetson Orin NX 开发指南(5): 安装 OpenCV 4.6.0 并配置 CUDA 以支持 GPU 加速
    滑动窗口最大值问题
    CORBA 架构体系指南(通用对象请求代理体系架构)​
    vue-cli 简单了解及使用
    关于android studio 新建项目 是否勾选 use legacy android.support libraries
    【ACWing】1401. 围住奶牛
    外包干了28天,技术退步明显......
    CF Round 479 (Div. 3)--D. Divide by three, multiply by two(离散化+拓扑排序)
    27.在springboot中使用thymeleaf的属性inline(text, javascript 和 none)
  • 原文地址:https://blog.csdn.net/weixin_62684026/article/details/126436924