Leetcode PHP题解--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。

最终代码

<?php
class 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);
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。