我用了一天时间,绞尽脑汁写出了AC的代码,满心欢喜去讨论区看看别人的思路,发现,这“哥德巴赫猜想”什么鬼?!!!!!!非素数可分解为两个或三个素数!!!!喂喂喂,裁判,这有人作弊!!!!
好吧,冷静下来,一研究,满嘴苦涩,我这是绕了个大弯啊!!!
这里先解释下“哥德巴赫猜想”,有兴趣的可以看看后面的我的非“哥德巴赫猜想”解法。
“哥德巴赫猜想”:任一大于2的偶数都可写成两个素数之和。还有,任一大于5的整数都可写成三个质数之和。
由此,可以知道:
1.两个站之间的距离 D 如果是素数,那站数+1;
2.D 不是素数,但它是偶数,那站数+2就可以了;
3.D 不是素数,是奇数。因为奇数=奇数+偶数,而2是唯一一个是偶数的素数,所以,如果D-2是素数的话,站数+2,否则+3;
4.最后,别忘了,始发站也算一站,把它加上,就是答案。
代码如下:
import java.util.*; public class Solution { /** * * @param n int整型 * @param a int整型一维数组 * @return int整型 */ //我用了两个哈希set保存素数和非素数,不用也能过,而且更快,内存也没有更大 public static HashSet<Integer> primes; public static HashSet<Integer> noprimes; public int work (int n, int[] a) { // write code here primes=new HashSet<Integer>(); noprimes=new HashSet<Integer>(); primes.add(1); int count=1; for(int i=0;i<n-1;i++){ int all=a[i+1]-a[i]; if(isPrime(all)){ count++; }else{ if(all%2==0){ count+=2; }else{ if(isPrime(all-2)){ count+=2; }else{ count+=3; } } } } return count; } public boolean isPrime(int n){ if(primes.contains(n)){ return true; } if(noprimes.contains(n)){ return false; } for(int i=2;i<=Math.sqrt(n);i++){ if(n%i==0){ noprimes.add(n); return false; } } primes.add(n); return true; } }
我的非“哥德巴赫猜想”解法,耗时1607ms,内存254444K。
import java.util.*; public class Solution { /** * * @param n int整型 * @param a int整型一维数组 * @return int整型 */ public static int[] primes; public int work (int n, int[] a) { // write code here //先把每段距离放到数组中,并得到最大的距离。 int max=0; int[] distance=new int[n-1]; for(int i=0;i&amp;amp;lt;n-1;i++){ distance[i]=a[i+1]-a[i]; if(distance[i]&amp;amp;gt;max){ max=distance[i]; } } //然后求出max以内的所有素数 //素数标0,非素数标上前一个素数的位置,这样遇到非素数可以快速地找到下一个素数 //素数的倍数肯定不是素数,从小到大一遍历,就只剩下素数了。 primes=new int[max+1]; //多分配一个元素,就是1对1,2对2,而不是0对1,1对2,盘逻辑的时候方便 int pre=1; for(int i=2;i&amp;amp;lt;=max/2;i++){ if(primes[i]==0){ for(int j=2;j&amp;amp;lt;=max/i;j++){ primes[i*j]=-1; } pre=i; }else{ primes[i]=pre; } } for(int i=max/2;i&amp;amp;lt;=max;i++){ if(primes[i]==0){ pre=i; }else{ primes[i]=pre; } } //这就是求最小数量,很简单 int count=1; for(int i=0;i&amp;amp;lt;n-1;i++){ if(primes[distance[i]]==0){ count++; }else{ count+=getMin(distance[i]); } } return count; } public int getMin(int n){ //先过一遍,如果能分解为两个素数最好了,直接返回2,顺便把素数都保存下来,下一步就省些事 ArrayList&amp;amp;lt;Integer&amp;amp;gt; al=new ArrayList&amp;amp;lt;Integer&amp;amp;gt;(); for(int i=n-1;i&amp;amp;gt;=n/2;i--){ if(primes[i]==0){ if(primes[n-i]==0){ return 2; }else{ al.add(i); } }else{ i=primes[i]+1; //因为每轮循环结束后都有i--,所以+1抵消下 } } //既然2不行,那最小的肯定是3,遇到3返回,遇不到只能先遍历着,最后返回最小值 int min=n; for(int i=0;i<al.size();i++){ int a=getMin(n-al.get(i))+1; if(a==3){ return 3; }else if(a<min){ min=a; } } return min; } }