634. Find the Derangement of An Array

LeetCode medium original: C# #array #csharp #dynamic-programming #hash-table #leetcode #math #medium #search

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

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

示例:

Input: n = 3

Output: 2

C# 解法

匹配/原始

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++ 解法

自动草稿，提交前请检查

#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 解法

匹配/原始

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 解法

匹配/原始

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 解法

匹配/原始

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 解法

匹配/原始

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]
}

Algorithm

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

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

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

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

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

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

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。