634. Find the Derangement of An Array

leetcode medium

#array#csharp#dynamic-programming#hash-table#leetcode#math#medium#search

Task

В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3

Output: 2

C# solution

matched/original

public class Solution {
    public int CountDerangements(int n) {
        const int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountDerangements(int n) {
        const int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        vector<int>& dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

Java solution

matched/original

public class Solution {
    public int countDerangements(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

JavaScript solution

matched/original

var countDerangements = function(n) {
    const MOD = 1e9 + 7;
    if (n === 0) return 1;
    if (n === 1) return 0;
    let dp = Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 0;
    for (let i = 2; i <= n; i++) {
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
    }
    return dp[n];
};

Python solution

matched/original

def countDerangements(n: int) -> int:
    MOD = 10**9 + 7
    if n == 0:
        return 1
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 0
    for i in range(2, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
    return dp[n]

Go solution

matched/original

package main

import "fmt"

func countDerangements(n int) int {
    const MOD = 1000000007
    if n == 0 {
        return 1
    }
    if n == 1 {
        return 0
    }
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 0
    for i := 2; i <= n; i++ {
        dp[i] = (i - 1) * (dp[i-1] + dp[i-2]) % MOD
    }
    return dp[n]
}

Explanation

Algorithm

Инициализация массива для хранения результатов

Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.

Вычисление количества отклонений

Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.

Возвращение результата

Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎