주간 챌린지 151

Challenge , My solutions

작업 #1 › 이진 트리 깊이

일

이진 트리가 제공됩니다.

최소 깊이를 찾는 스크립트를 작성하십시오. 최소 깊이는 루트에서 가장 가까운 리프 노드(자식이 없는 노드)까지의 노드 수입니다.

내 솔루션

challenge 145 의 eertree 작업과 마찬가지로 원하는 결과를 얻기 위해 이 작업을 부끄럽게도 단축하고 있습니다.

이러한 이진 트리 작업에서 가장 어려운 점은 트리 자체로 작업하는 것이 아니라 의미 있는 입력을 트리 개체로 변환하는 것입니다. 입력을 결정했다면 3개 항목(값, 왼쪽, 오른쪽) 중첩 배열(입력에서 YAML 또는 JSON으로 구문 분석)이 됩니다. 예를 들어 첫 번째 예는 [1, [2, 4, 5], 3] 이고 두 번째 예는 [1, [2, [4, null, 6]], [3, null, 5]]입니다. ) .

그러나 이 작업의 경우 각 행이 파이프 문자로 구분되고 값이 공백으로 구분되는 예상 입력 형식이 제공됩니다.

내 솔루션에서 입력을 rows 변수로 나눕니다. 각 행에 대해 공백으로 분할하고 배열이 짧으면 채우고 해당 행에서 * 쌍을 찾으면 종료합니다.

예

$ ./ch-1.py "1 | 2 3 | 4 5"
2

$ ./ch-1.py "1 | 2 3 | 4 *  * 5 | * 6"
3

$ ./ch-1.pl "1 | 2 3 | 4 *  * 5 | * 6"
3

작업 #2 › 롭 더 하우스

일

당신은 항상 첫 번째 집에서 시작하여 같은 방향으로 움직이는 일련의 집을 털 계획입니다. 그러나 인접한 두 집을 강탈할 수는 없습니다.

달성할 수 있는 가장 높은 이득을 찾는 스크립트를 작성하십시오.

내 솔루션

나는 세컨드 하우스가 되고 싶다. 그들은 결코 약탈당하지 않습니다 :-)

나는 이러한 유형의 도전을 정말 좋아합니다. 왜냐하면 그것은 당신이 그것을 해결하는 가장 좋은 방법에 대해 생각하게 하기 때문입니다. 따라서 설명으로 첫 번째 집을 약탈한 후 세 번째 집을 방문하거나(인접한 두 집을 강탈할 수 없기 때문에) 네 번째 집을 방문할 수 있습니다. 1집 이후에 더 많은 집을 약탈한다면 중급 집을 방문하는 것이 더 유리할 것입니다. 예를 들어 5하우스를 약탈했다면 3하우스도 했어야 합니다.

그래서 이를 염두에 두고 지금까지의 haul과 남은 집 목록을 입력으로 받아 가장 큰 haul을 반환하는 재귀 함수rob를 사용했습니다. 각 호출에 대해 하나 또는 두 개의 하우스를 건너뛰고 최대 견인 결과를 반환하는 결과를 반환합니다.

예

$ ./ch-2.py 2 4 5
7

$ ./ch-2.py 4 2 3 6 5 3
13

$ ./ch-2.pl 4 2 3 6 5 3
13