提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

素数判断——数论

2023-02-18 16:26:27 时间

前言

今天的题还是有点难度的，毕竟剑指offer不是吃素的，我感觉这个题目应该十分接近蓝桥杯的难度了，或者是已经超过了蓝桥杯的难度，但是刷的题中题，方为人中人，发车了

解题报告

1.剑指offer49丑数 算是一个比较新的概念，我刚看这个题的时候，就只想到了暴力解法，循环判断，先写一个函数IsChou来判断是不是丑数，再从1开始递增找第1500位的丑数。

//暴力解法
#include<iostream>
using namespace std;
bool IsChou(int numbur)
{
	while (numbur % 2 == 0)
		numbur /= 2;
	while (numbur % 3 == 0)
		numbur /= 3;
	while (numbur % 5 == 0)
		numbur /= 5;
	return numbur == 1 ? true : false;
}
int GetUglyNumbur(int n)
{
	if (n <= 0)
		return 0;
	int numbur=0;
	int uglyFound = 0;
	while (uglyFound < n)
	{
		++numbur;
		if (IsChou)
			++uglyFound;
	}
	return numbur;
}
int main()
{
	cout << GetUglyNumbur(1500);
	
	return 0;
}

但是很遗憾没有拿满分，翻开我那几乎积灰的剑指offer，看到这个题是放到了用空间换时间的算法中，又想了想，之所以会超时，是因为上面的题解中计算了许多不是丑数的数据，再看丑数的定义是，应该是另一个丑数乘以2，3，5的结果，进行优化

int GetUglyNumber2(int n)
{
	if (n <= 0)
		return 0;
	int *pUglyNumber = new int[n];
	pUglyNumber[0] = 1;
	int nextUglyNumber = 1;//下一个
	int *pMulitiply2 = pUglyNumber;
	int *pMulitiply3 = pUglyNumber;
	int *pMulitiply5 = pUglyNumber;

	while (nextUglyNumber < n)
	{
		int mmin = Min(*pMulitiply2 * 2, *pMulitiply3 * 3, *pMulitiply5 * 5);
		pUglyNumber[nextUglyNumber] = mmin;

		while (*pMulitiply2 * 2 <= pUglyNumber[nextUglyNumber])
			++pMulitiply2;
		while (*pMulitiply3 * 3 <= pUglyNumber[nextUglyNumber])
			++pMulitiply3;
		while (*pMulitiply5 * 5 <= pUglyNumber[nextUglyNumber])
			++pMulitiply5;

	}
	int ugly = pUglyNumber[nextUglyNumber - 1];
	delete[]pUglyNumber;
	return ugly;
}
int Min(int number1, int number2, int number3)
{
	int min = (number1 < number2) ? number1 : number2;
	min = (min < number3) ? min : number3;

	return min;
}
//来自剑指offer

相关文章