《算法零基础》Day07：素数判定

今天课多，做题时间短，没有优化，只会笨比做法。。

• 前言
• LeetCode 886.回文素数
• • 分析
  • 代码
• 剑指Offer 49. 丑数
• • 分析
  • 代码

原题链接: 886.回文素数

封装两个函数，分别判断是否为素数，是否为回文数
1.判断素数方法是 从2开始加加，来判断与传进来的数num的关系，如果范围内所有数都不能整除num，num就是素数

2.回文数，是把整型数字放入字符数组中，利用首位两个指针来判断是否为回文数。

3.如果数字在范围10000000到100000000内，就会有超时报错情况，那直接跳过就好

//判断素数
bool IsPrime(int num)
{
    if (num <= 1)
    return false;
    for (int i = 2; (i * i) <= num; ++i)
    {
        if (num % i == 0)
        return false;
    }
    return true;
}

//判断回文数
int IsPalindrome(int n)
{
	char nums[20];
	sprintf(nums, "%d", n);
	int left = 0, right = strlen(nums) - 1;

	while (left < right)
    {
		if (nums[left] != nums[right])
        {
			return false;
		}
		left++;
		right--;
	}
	return true;
}

int primePalindrome(int n)
{
    while (n)
    {
        if (n >= 10000000 && n < 100000000)
        {
            n = 100000000;
        }
        if (!IsPrime(n))
        {
            ++n;
            continue;
        }
        if (!IsPalindrome(n))
        {
            ++n;
            continue;
        }
        break;
    }

    return n;
}

链接: 剑指Offer 49. 丑数

链接: LeetCode 264.丑数||

根据题目要求，包含质因子2，3，5的叫做丑数。那先手写一下前几个

初始，丑数为{1}，1可以同2，3，5相乘，取最小的1×2添加到丑数序列中。

现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以再没必要再比较1×2了。

现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但是2×3和2×5是没必要比较的，因为有比它更小的1可以同3，5相乘，所以我们只需要比较1×3，1×5，2×2。取最小的1×3放入丑数数组中。

做法：利用三个指针p2, p3, p5
代表第 i 个数的2倍，3倍数，5倍，取最小的放入数组中

C语言版动态方程：

dp[i] = fmin(dp[p2]*2, fmin(dp[p3]*3, dp[p5]*5));

int nthUglyNumber(int n)
{
    int dp[n + 1];
    dp[0] = 1;
    
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; ++i)
    {
        dp[i] = fmin(dp[p2] * 2, fmin(dp[p3] * 3, dp[p5] * 5));
        if (dp[i] == dp[p2] * 2)
        p2++;
        if (dp[i] == dp[p3] * 3)
        p3++;
        if (dp[i] == dp[p5] * 5)
        p5++;
    }

    return dp[n - 1];
}

明天见