title: 【每日一题】LeetCode 263.丑数
tags:

  • leetcode
  • acwing
  • 每日一题
    abbrlink: 72212b99
    date: 2021-04-10 15:42:50

LeetCode 263.丑数

思路

模拟题，根据题目条件写判断即可

C++代码

  1. class Solution {
  2. public:
  3.     bool isUgly(int n) {
  4.         if(n<=0)    return false;
  5.         while(n%2==0)   n/=2;
  6.         while(n%3==0)   n/=3;
  7.         while(n%5==0)   n/=5;
  8.         if(n==1)    return true;
  9.         else
  10.             return false;
  11.     }
  12. };

AcWing 62.丑数

思路

这里要求第n个丑数，对于效率的要求就更高了，但是思路依然是比较清晰，就是在数组里面把2，3，5从小到大的数用集合存起来，然后根据性质还有升序的规则一个一个的算出来即可（三路归并）但是这三路里面是有重合的，所以在写的时候还要考虑一下去重的问题，最后得到的这个总的集合就是所有只包含2，3，5为质因子

C++代码

  1. class Solution {
  2. public:
  3.     typedef long long ll;
  4.     int getUglyNumber(int n) {
  5.         if(n<2)    return n;
  6.         vector<int> f(1,1);
  7.         int i=0,j=0,k=0;
  8.         ll t=0;
  9.         while(--n)
  10.         {
  11.             t=min(f[i]*2, min(f[j]*3,  f[k]*5));
  12.             if(t==f[i]*2)   i++;
  13.             if(t==f[j]*3)   j++;
  14.             if(t==f[k]*5)   k++;
  15.             f.push_back(t);
  16.         }
  17.         return f.back();
  18.     }
  19. };