내가 여기서 하고 있는 도전에 대한 모든 코드:

루아프 / leetcode-jan-2021

leetcode-jan-2021

View on GitHub



이 문제에 대해 쓰는 습관이 30일을 마무리하는 데 도움이 되기를 바라며 이 시리즈를 하고 있습니다. 또한 이 작업을 수행하는 동안 Python 지식을 향상시키고 있으므로 코드가 끔찍하게 보이면 죄송합니다! 나는 매일 시간을 제한하여 해결책이 최선의 노력일 뿐 최선의(또는 특히 좋은) 해결책이 되지 않도록 합니다.

문제

LeetCode Link

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

내 테스트

import pytest
from .Day1 import Solution

s = Solution()


@pytest.mark.parametrize(
    "arr,pieces", [([49, 18, 16], [[16, 18, 49]]), ([1, 3, 5, 7], [[2, 4, 6, 8]])]
)
def test_cannot_form_array(arr, pieces):
    assert not s.canFormArray(arr, pieces)


@pytest.mark.parametrize(
    "arr,pieces",
    [
        ([], []),
        ([85], [[85]]),
        ([15, 88], [[88], [15]]),
        ([91, 4, 64, 78], [[78], [4, 64], [91]]),
    ],
)
def test_can_form_array(arr, pieces):
    assert s.canFormArray(arr, pieces)

내 솔루션

from typing import List


class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        index = 0
        new_index = index
        pieces_m = pieces
        while index < len(arr):
            curr = arr[index]
            for a in pieces_m:
                if a[0] == curr and a == arr[index : index + len(a)]:
                    new_index += len(a)
                    pieces_m.remove(a)
            if new_index == index:
                return False
            else:
                index = new_index
        return True

분석

내 해설

성능은 끔찍하지 않은 것 같지만 메모리 사용량은 꽤 나빴습니다.

내가 그것에 대해 생각한 방식은 배열을 반복하면 해당 값으로 시작하는 조각이 있는지 확인하는 것입니다. 그렇다면 일치하는 다음 세그먼트를 확인하십시오. 일치하는 항목이 있으면 인덱스를 세그먼트의 끝으로 범프합니다. 일치하는 항목이 없으면 단락됩니다.

나는 파이썬을 처음 접했지만 메모리에서 가격을 지불했을 수도 있는 한 곳은 arr[index : index + len(a)] 이라고 생각합니다. 매번 새 목록이 생성되는지 조사하고 확인해야 합니다.

나는 실제로 2개의 솔루션(그 주에 대한 보너스 솔루션)을 수행하고 저녁에 할당된 시간을 초과했기 때문에 그날 가장 쉬운 솔루션에서 멈췄습니다. 여기에 글을 쓴 후 생각해보면 대부분의 다른 문제와 마찬가지로 dict(HashMap)을 사용하여 더 빠르게 만들 수 있었습니다. 도전이 끝난 후 기회를 줄 수 있습니다.