题目:车站建造问题
描述:X轴上10^8个点,从左到右依次编号为0~10^8-1,相邻点距离为1,其中有n个点有特殊意义,从小到大依次为a0 ~ an-1,其中保证a0=0.
现在需要建设收集站,有两个要求必须被满足:
1、每个有意义的点必须修建收集站。
2、相邻收集站的距离必须为1或为某个质数。
现给出n和a数组,求需要建设收集站的最小数量。
示例1:输入:3,[0,7,11]
返回值:4
说明:在0,7,8,11处建造收集站,差值分别为7,1,3,符合要求

解法一:
思路分析:首先分析题目,题目的意思是在一个x轴上,有10^8个点,每个点都有编号,现在需要在点上建造收集站,建造的收集站满足两个条件,1、在有意义上的点必须建造收集站,有意义的点,题目已经给出,2、相邻收集站之间的距离必须为1或者为某个质数,质数的概念是一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,满足这两个条件即可,求需要建设收集站的最小数量。
——首先考虑既然要计算收集站的最小数量就需要设定一个count的值用来记录数量,这道题是一道关于质数的题目,既然需要判断两个点之间的距离,所以我们不妨设count的数值为1,因为有意义的点必须建造收集站,其次我们需要考虑两个点之间的差值是否为质数,这时我们就需要一个关于判断质数的函数,这个函数很好写,就不单独进行书写了,下面直接进行判断。
——如果两点之间的距离为质数,那么我们就不需要判断,直接将count的值加1即可。
——接下来判断如果两个数之间的差值不是质数的话,如果是偶数,假如为7,11的两个有意义的点,之间的差值为4,那么只需要在两个整数值之间插入一个偶数8即可,这样差值就变成了1和3符合题意,这里我们应该会想到哥德巴赫猜想:任意大于2的偶数都可写成两个质数之和,所以在这儿我们直接将count的值加2即可实现。
——下面当两个数之间的差值是奇数,在这里我们考虑到2是唯一的一个即是偶数又是质数的数,所以我们将距离的值dist - 2继续进行判断,当判断的结果为质数,那么只需要将count的值加2即可,如果不是质数的话,我们想一想,如果dist的值为11,那么dist - 2 = 9,9不是质数,那么9可以分成两个距离的和,还有另外一个质数2,那么就需要三个了,所以只要将count的值加3即可。(哥德巴赫猜想的一部分任意大于5的整数都可写成三个质数之和)
下面我们进行验证,实例分析,输入:3,[0,7,11]:
图片说明
——根据上述表格分析,我们可以得出最终输出的count为4。
python核心代码:

import math
#
# 
# @param n int整型 
# @param a int整型一维数组 
# @return int整型
#
class Solution:
    def work(self , n , a ):
        # write code here
        def isprime(mouth):#判断是否为质数
            if mouth == 1:
                return False
            for i in range(2,math.floor(math.sqrt(mouth)) + 1):#math.floor()为向下取整
                if mouth % i == 0:
                    return False
            return True
        count = 1#初始站也算一站
        for i in range(1, n):
            dist = a[i] - a[i - 1]#两点之间的距离
            if isprime(dist) or dist == 1:#如果是质数,直接加1即可
                count += 1
            elif dist % 2 == 0:#如果是偶数,直接加2即可
                count += 2
            else:
                if isprime(dist - 2):#2是偶数也是唯一的素数,如果dist - 2是素数的话,count + 2
                    count += 2
                else:#否则加3
                    count += 3
        return count

——在上述程序中,有一个判断质数的程序,判断质数程序的时间复杂度为,下面还有一个for循环图片说明,所以总的时间复杂度为图片说明 。没有用到存储空间,所以空间复杂度为