题解 | #车站建造问题#
车站建造问题
http://www.nowcoder.com/practice/9fededa1b63a41798e5d43344d7bf216
车站建造问题
描述
X轴上10^8个点，从左到右依次编号为0~10^8-1，相邻点距离为1，其中有n个点有特殊意义，从小到大依次为a0~an-1，其中保证a0=0.现在需要建设收集站，有两个要求必须被满足：
1、每个有意义的点必须修建收集站。
2、相邻收集站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设收集站的最小数量。
示例
输入：3,[0,7,11]
返回值：4
说明：在0,7,8,11处建造收集站，差值分别为7,1,3，符合要求
方法一
思路分析
本题需要用到数学的办法，相邻收集站的距离必须为1或者某个质数，因此循环遍历数组，如果数组相邻位置的距离不为质数，那么在这两个位置之间修建收集站，修建收集站的数量与两个位置的距离有关，设置这个距离为distance，那么分为以下两种情况：如果distance为偶数，根据哥德巴赫猜想，大于2的偶数可以分为两个质数的和
如果distance为奇数，任何大于5的奇数都是三个质数的和
因此有以下步骤:
- 首先设置修建收集站的个数count=n
- 循环遍历数组，如果相邻位置的距离distance为质数不进行操作；
- 如果distance不为质数，那么分为两种情况：
- 如果distance为偶数，那么需要插入两个收集站，因此count+2
- 如果distance为奇数，可将其拆分为：（distance-2）+2的形式，又可分为两种情况：
2.（distance-2）如果不为质数，那么 将其拆分为(distance-1)+1，(distance-1)为偶数，偶数可分为两个质数的和，因此这种情况下需要修建三个收集站，即count+3
上面由于初始化设置count=n，因此在实际操作中插入两个收集站只需要加1，插入三个收集站只需要加2即可
图解
核心代码
class Solution {
public:
/**
*
* @param n int整型
* @param a int整型一维数组
* @param aLen int a数组长度
* @return int整型
*/
int work(int n, int* a, int aLen) {
// write code here
int count=n;
for(int i=0;i<n-1;i++)
{
int distance=a[i+1]-a[i];
if(distance!=1&&prime(distance)==0)//distance不为质数，那么分为两种情况
{
if(distance%2==0||prime(distance-2)==1)//distance为偶数或者distance-2为质数，那么需要插入两个收集站，因此count+2
count++;
else count=count+2;
}
}
return count;
}
int prime(int n)//判断是否为素数
{
if (n == 1)
{
return 0;
}
for(int i = 2; i*i <= n; i++)//只需要判断到平方根n即可
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
}; 复杂度分析
- 时间复杂度：该方法的时间在于判断相邻位置的距离是否为质数，判断一个质数的时间复杂度为
，需要遍历数组，因此总的时间复杂度为
- 空间复杂度：空间复杂度为$O(1)$
