D124 1175. Prime Arrangements
题目链接
1175. Prime Arrangements
题目剖析
这道题，给一个数字n，生成一个从1到n的数组，有多少种排列形式使得 质数位的数字为质数？其中1<=n<=100
因为最终返回值可能比拟大，请返回mod(10**9 +7)后的后果。
思路
也就是说，在质数位的数字是能够任意排列的，而剩下的非质数位也是能够任意排列的，因而咱们离开计算两种状况，再相乘就能够了。
因为n的范畴到100，因而能够手写质数，用空间换工夫。
其次，咱们须要晓得，给定的数字n及之前有多少个质数。这个比较简单，只须要把咱们在后面生成的质数数组的键和值用array_flip函数颠倒过去就能够了。失去后，应用阶乘就能够算出排列数。
对于非质数，咱们用range函数生成1到100的值，而后用array_diff函数生成非质数数组。值减去键就是非质数的个数。
因而，咱们先用is_set判断给出的n是在质数数组还是在非质数数组外面。在质数数组的话，间接把n当作键，去数组里获取值就能够了。在非质数数组的话，从非质数数组把n当键获取值+1，即可失去n及之前有多少个非质数了。为什么要+1是因为array_diff返回的是下标是从0开始的。n减去非质数数字个数就等于质数个数了。
好了，当初有了质数数量和非质数数量，须要做的是阶乘了。咱们都晓得阶乘后的值回升的十分快，所以我采纳的是每乘一个数字就取一次模。
先用range函数生成须要参加阶乘的数字，再用array_values获取这些数字，最初用array_reduce把一维数组变成一个数。这里质数和非质数一样，就不多做解释了。
须要留神的是，n的返回中包含1，也就是说会呈现质数数量为0的状况。此时进行array_reduce的话，会返回0。再进行相乘的话，会返回0。因而我在计算后还用max函数设置了最小值为1。
最终代码
<?phpclass Solution { /** * @param Integer $n * @return Integer */ function numPrimeArrangements($n) { $primes = [1 =>2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]; $nonPrimes = array_values(array_diff(range(1,100), $primes)); $primesBeforeIndex = array_flip($primes); $nonPrimesBeforeIndex = array_flip($nonPrimes); if(isset($primesBeforeIndex[$n])){ $primeAmount = $primesBeforeIndex[$n]; $nonePrimeAmount = $n - $primeAmount; } else{ $nonePrimeAmount = $nonPrimesBeforeIndex[$n]+1; $primeAmount = $n - $nonePrimeAmount; } $primesPermutation = array_reduce(array_values(range(1,$primeAmount)), function($carry, $item){ $carry *= $item; return $carry%(pow(10,9)+7); },1); $primesPermutation = max(1, $primesPermutation); $nonPrimePermutation = array_reduce(array_values(range(1,$nonePrimeAmount)), function($carry, $item){ $carry *= $item; return $carry%(pow(10,9)+7); },1); $nonPrimePermutation = max(1, $nonPrimePermutation); return ($primesPermutation * $nonPrimePermutation)%(pow(10,9)+7); }}若感觉本文章对你有用，欢送用爱发电赞助。