leetcode学习记录_丑数

丑数

263. 丑数
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
来源：力扣（LeetCode）
根据丑数的定义，可以很容易想到，如下代码，把参数的所有2、3、5的因数通过除法去掉，如果最后剩下1，就代表这个数是丑数

class Solution {
public:
    bool isUgly(int n) {
		if(n <= 0) return false;
		while(1)
		{
		if(n == 1) return true;
		if(n % 2 == 0) n>>1;
		else if(n % 3 == 0) n/=3;
		else if(n % 5 == 0) n/=5;
		else return false;
		}
    }
};

264. 丑数 II
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
这一题不是判断，而是求丑数，所以如果用上一题的思路去写，效率就hi很低，我们还是从丑数的定义下手，丑数的质因数只有2、3、5，换种说法，丑数是由若干个2、3、5乘起来得到的，由此得出以下代码

class Solution {
public:
    int nthUglyNumber(int n) {
		vector<int>nums;
		nums.emplace_back(1);
		int p2 = 0,p3 = 0,p5 = 0;
		for(int idx = 1;idx < n;idx++)
		{
			int data = min(nums[p2]*2,min(nums[p3]*3,nums[p5]*5)) ;
			nums.emplace_back(data);
			if(nums[idx] == nums[p2]*2) p2++;
			if(nums[idx] == nums[p3]*3) p3++;
			if(nums[idx] == nums[p5]*5) p5++;
		}
		return nums[n-1];
    }
};