题解 | #车站建造问题#

题目：车站建造问题
描述：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循环，所以总的时间复杂度为 。没有用到存储空间，所以空间复杂度为。