День 3 – прекрасная аранжировка

Проблема

Предположим, у вас есть n Целые числа помечены 1 через n Анкет Перестановка этих n Целые числа перми ( 1-индексированный ) считается Красивая аранжировка Если для каждого я (1) , Либо из следующего верно:

• перми [i] делится i .
• я делится на перми [i] Анкет

Дано целое число n Верните номер прекрасных композиций, которые вы можете построить.

Пример: 1

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

Пример 2:

Input: n = 1
Output: 1

Мои тесты

import pytest
from .Day3 import Solution

s = Solution()


@pytest.mark.parametrize("input,expected", [(2, 2), (1, 1), (3, 3), (4, 8)])
def test_gives_number_of_beautiful_arrangements(input, expected):
    assert s.countArrangement(input) == expected

Мое решение

def check(n: int, index: int, checking: dict) -> int:
    if index == 0:
        return 1
    total = 0

    for i in range(1, n + 1):
        if (i not in checking or not checking[i]) and (i % index == 0 or index % i == 0):
            checking[i] = True
            total += check(n, index - 1, checking)
            checking[i] = False
    return total


class Solution:
    def countArrangement(self, n: int) -> int:
        checking = {}
        return check(n, n, checking)

Анализ

Мой комментарий

Это снижается как «средняя» сложность, но я нашел это довольно сложно. Мое решение может быть намного лучше Но это лучшее, что я смог справиться за время, которое у меня было.

Я решил рано, что мне нужно сделать 2 вещи. Я должен был бы перекончить с «списком», и мне пришлось бы проверить каждый номер по каждому индексу.

Я решил сделать карту номера 1 к n и рекурсивно проверяйте каждый номер, установив флаг на карте, чтобы помочь пропустить этот номер в рекурсивных вызовах.

Таким образом, идея состоит в том, что начиная с 1, проверьте все число в списке, чтобы увидеть, выполняют ли они требование:

• перми [i] делится i .
• я делится на перми [i] Анкет

Мы установили индекс на n и уменьшить его в каждом рекурсивном вызове Проверьте по номеру n . Итак, каждый номер n рекурсивно проверяет каждый индекс. Теперь мы получаем подсчет каждый раз, когда требования выполняются для числа и индекса вплоть до последнего индекса. Это дает нам подсчет всех действительных Красивые аранжировки Анкет

Оригинал: “https://dev.to/ruarfff/day-3-beautiful-arrangement-11l0”