素数判断——数论
前言
今天的题还是有点难度的，毕竟剑指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本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-10-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
