关于leetcode:Leetcode-PHP题解D124-1175-Prime-Arrangements

3次阅读

共计 1750 个字符，预计需要花费 5 分钟才能阅读完成。

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);
    }
}

若感觉本文章对你有用，欢送用爱发电赞助。

正文完