526. Beautiful Arrangement

LeetCode medium original: C# #array #backtracking #csharp #leetcode #medium #recursion

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:

perm[i] делится на i.

i делится на perm[i].

given entier n, return количество красивых перестановок, которые вы можете создать.

Exemple:

Input: n = 2

Output: 2

Explanation:

The first beautiful arrangement is [1,2]:

- perm[1] = 1 is divisible by i = 1

- perm[2] = 2 is divisible by i = 2

The second beautiful arrangement is [2,1]:

- perm[1] = 2 is divisible by i = 1

- i = 2 is divisible by perm[2] = 1

C# solution

correspondant/original

public class Solution {
    private int count = 0;
    
    public int CountArrangement(int N) {
        int[] nums = Enumerable.Range(1, N).ToArray();
        Permute(nums, 0);
        return count;
    }
    
    private void Permute(int[] nums, int l) {
        if (l == nums.Length) {
            count++;
        }
        for (int i = l; i < nums.Length; i++) {
            Swap(nums, i, l);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                Permute(nums, l + 1);
            }
            Swap(nums, i, l);
        }
    }
    
    private void Swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#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:
    private int count = 0;
    
    public int CountArrangement(int N) {
        vector<int>& nums = Enumerable.Range(1, N).ToArray();
        Permute(nums, 0);
        return count;
    }
    
    private void Permute(vector<int>& nums, int l) {
        if (l == nums.size()) {
            count++;
        }
        for (int i = l; i < nums.size(); i++) {
            Swap(nums, i, l);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                Permute(nums, l + 1);
            }
            Swap(nums, i, l);
        }
    }
    
    private void Swap(vector<int>& nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}

Java solution

correspondant/original

public class Solution {
    int count = 0;
    public int countArrangement(int N) {
        int[] nums = new int[N];
        for (int i = 1; i <= N; i++)
            nums[i - 1] = i;
        permute(nums, 0);
        return count;
    }
    public void permute(int[] nums, int l) {
        if (l == nums.length) {
            count++;
        }
        for (int i = l; i < nums.length; i++) {
            swap(nums, i, l);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0)
                permute(nums, l + 1);
            swap(nums, i, l);
        }
    }
    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}

JavaScript solution

correspondant/original

var countArrangement = function(N) {
    let count = 0;
    const nums = Array.from({ length: N }, (_, i) => i + 1);
    
    function permute(l) {
        if (l === N) {
            count++;
            return;
        }
        for (let i = l; i < N; i++) {
            [nums[i], nums[l]] = [nums[l], nums[i]];
            if (nums[l] % (l + 1) === 0 || (l + 1) % nums[l] === 0) {
                permute(l + 1);
            }
            [nums[i], nums[l]] = [nums[l], nums[i]];
        }
    }
    
    permute(0);
    return count;
};

Python solution

correspondant/original

class Solution:
    def __init__(self):
        self.count = 0

    def countArrangement(self, N: int) -> int:
        nums = list(range(1, N + 1))
        self.permute(nums, 0)
        return self.count
    
    def permute(self, nums, l):
        if l == len(nums):
            self.count += 1
        for i in range(l, len(nums)):
            nums[i], nums[l] = nums[l], nums[i]
            if nums[l] % (l + 1) == 0 or (l + 1) % nums[l] == 0:
                self.permute(nums, l + 1)
            nums[i], nums[l] = nums[l], nums[i]

Go solution

correspondant/original

func countArrangement(N int) int {
    count := 0
    nums := make([]int, N)
    for i := 1; i <= N; i++ {
        nums[i-1] = i
    }
    permute(nums, 0, &count)
    return count
}

func permute(nums []int, l int, count *int) {
    if l == len(nums) {
        *count++
    }
    for i := l; i < len(nums); i++ {
        nums[i], nums[l] = nums[l], nums[i]
        if nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0 {
            permute(nums, l + 1, count)
        }
        nums[i], nums[l] = nums[l], nums[i]
    }
}

Algorithm

Инициализация и подготовка tableauа:

Создайте tableau чисел от 1 до N и инициализируйте счетчик красивых перестановок.

Создайте функцию для перестановки elementов tableauа.

Рекурсивное создание перестановок и проверка условий:

Напишите рекурсивную функцию для создания всех возможных перестановок tableauа, начиная с текущей позиции l.

На каждом шаге перестановки проверяйте, удовлетворяет ли текущий element условиям делимости. Если Énoncé выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

Возврат результата:

В основной функции вызовите рекурсивную функцию с начальной позицией 0 и return значение счетчика красивых перестановок.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.