3일차 - 아름다운 배열

7262 단어 pythonleetcode

문제



Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

  • perm[i] is divisible by i.
  • i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.



예: 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 to n의 맵을 만들고 재귀 호출에서 해당 번호를 건너뛸 수 있도록 맵에 플래그를 설정하여 각 번호를 재귀적으로 확인하기로 결정했습니다.

따라서 아이디어는 1부터 시작하여 목록의 모든 숫자가 요구 사항을 충족하는지 확인하는 것입니다.

  • perm[i] is divisible by i.
  • i is divisible by perm[i].


인덱스를 n로 설정하고 숫자 check에서 n로 재귀 호출할 때마다 인덱스를 감소시킵니다. 따라서 각 숫자n는 모든 인덱스에 대해 재귀적으로 확인합니다. 이제 우리는 마지막 인덱스까지 숫자와 인덱스에 대한 요구 사항이 충족될 때마다 카운트를 얻습니다. 이것은 우리에게 유효한 모든 Beautiful Arrangemnts의 실행 카운트를 제공합니다.

좋은 웹페이지 즐겨찾기