1175. 質數排列 / 劍指 Offer II 104. 排列的數目

1175. 質數排列【簡單題】【每日一題】

思路：

求出質數的個數k1，n-k1求出非質數個數k2，則符合要求的種類個數是 k1的階乘 * k2的階乘，由於運算結果可能越界，因此根據題意對運算結果取10^9+7模。
設 MOD = 10^9+7,因此上述運算結果可錶示為：

ans = (k1! * k2!) % MOD

由於階乘運算過程中也可能越界，因此對上式進行數學變換

ans = (k1! * k2!) % MOD
	= ((k1! % MOD) * (K2! % MOD)) % MOD
	//【】錶示累乘
	= ((【k1i % MOD】 % MOD ) * (【k2i % MOD】 % MOD ) ) % MOD
	= (【k1i % MOD】 * 【k2i % MOD】) % MOD

代碼：

class Solution {
    
    static int MOD = (int) 1e9+7;
    public int numPrimeArrangements(int n) {
    
        if (n <= 2){
    
            return 1;
        }
        int k1 = 1;
        for (int i = 3; i <= n; i++) {
    
            if (isPrime(i)){
    
                k1++;
            }
        }
        int k2 = n - k1;
        long ans = 1;
        for (int i = 2; i <= k1; i++) {
    
            ans = ans * i % MOD;
        }
        for (int i = 2; i <= k2; i++) {
    
            ans = ans * i % MOD;
        }
        return (int) (ans);
    }
    public boolean isPrime(int n){
    
        int k = (int) Math.sqrt(n);
        for (int i = 2; i <= k ; i++) {
    
            if (n % i == 0){
    
                return false;
            }
        }
        return true;
    }
}

---

劍指 Offer II 104. 排列的數目【中等題】

思路：【動態規劃】

被昨天背的完全背包公式給騙了~，這個題不是背包問題

代碼：

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        //定義dp數組，dp[i]錶示和為i的組合數
        int[] dp = new int[target+1];
        //邊界條件 i = 0時，和為0的組合只有一種情况就是 不選任何元素，因此dp[0] = 1
        dp[0] = 1;
        //轉移方程
        for (int i = 1; i <= target; i++) {
    
            for (int num : nums) {
    
                //遍曆nums數組，如果目標和i大於等於當前元素值num，說明這個元素可以被選用dp[i]的值等於數組中所有滿足i>=num的dp值之和
                if (i >= num) {
    
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}