나는 배우는 동안이 질문을 보았고 그것을 해결할 수 없습니다. 문제-서로 다른 크기의 벽이 bricks나중에 각각 쌓인 매트릭스 표현이 주어졌습니다 . 위에서 아래로 절단 할 최소 절단을 어떻게 알 수 있습니까? (가능한 한 조인트 라인을 활용한다는 것을 의미하는 최소한의 노력)
예-[[3,5,1,1], [2,2,4,2], [4,4,2], [1,3,3,3], [1,1,6,1, 2]] 답 : 2. 관절에서 자르기가 더 쉽기 때문에. (이미지가 너무 커서 죄송합니다.)
나는 조언을 구하려는 시도를 게시했습니다.
def fewer_cut(walls):
cut = 0
for row in wall:
length =0
for brick in row:
length = length+ brick
cuts += 1
이것을 시도하고 알려주시겠습니까? 설명 : 이 문제를 다른 관점에서 생각하면 각 컷 이 다른 레이어 more joints사이 two bricks를 어떻게 통과 할 수 있습니까? 그러면 해결책을 찾는 것이 더 쉽습니다.
우리는 벽의 각 행을 반복하고 마지막 행을 제외하고 각 행 (지금까지) 이후에 포함 된 누적 거리에 대해 맵 테이블의 개수를 증가 시키려고합니다. 가장 큰 값을 가진 맵의 키는 가장 적은 컷이있는 수직선입니다. 그런 다음 전체 벽 크기에서이 값을 빼고 최종 답을 얻을 수 있습니다. 실행 시간은 O(n)우리가 벽을 한 번만 횡단하기 때문입니다.
from collections import defaultdict
def fewer_cut(walls):
''' minimum cut of layers of walls '''
N = len(walls) + 1 # offset 1
cuts = defaultdict(int)
for row in walls:
length = 0
for brick in row[:-1]:
length += brick
cuts[length] += 1
#print(cuts) # comment out later.
return N - max(cuts.values())
if __name__ == '__main__':
walls = [[3, 5, 1, 1],
[2, 2, 4, 2],
[4, 4, 2, 2],
[1, 3, 3, 2],
[1, 1, 6, 1, 1,]]
print(fewer_cut(walls))
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다