간격 최대화

주간 챌린지 298

매주 Mohammad S. Anwar는 우리 모두가 두 가지 주간 작업에 대한 해결책을 생각해 낼 수 있는 주간 챌린지를 보냅니다. 이는 우리 모두가 코딩을 연습할 수 있는 좋은 방법입니다.

도전, 나의 솔루션

작업 1: 최대제곱

일

0과 1만 있는 m x n 이진 행렬이 제공됩니다.

1만 포함된 가장 큰 정사각형을 찾아 그 면적을 반환하는 스크립트를 작성하세요.

내 솔루션

주요 기능은 행렬의 각 행에 대한 올바른 수의 열이 있는지 확인하는 것부터 시작됩니다

def maximal_square(matrix: list[list[int]]) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_size = 0

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

그런 다음 행렬의 각 셀을 반복합니다. 해당 셀의 항목이 1이면 해당 위치에서 시작하는 사각형의 크기를 확인합니다. max_side 변수도 범위를 벗어나지 않도록 계산됩니다. maximum_size 값을 추적하고 가장 큰 값을 반환합니다.

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 1:
                max_side = min(rows-row, cols-col)
                size = find_square_from_point(matrix, row, col, max_side)
                if size > maximum_size:
                    maximum_size = size

    return maximum_size

find_square_from_point 함수를 제대로 맞추는 것이 답답했습니다. 나는 실제로 만족스러운 해결책을 찾기 전에 몇 차례의 작업을 거쳤습니다. 논리는 매우 간단합니다. 정사각형을 고려해보세요:

. b c d
b b c d
c c c d
d d d d

정사각형의 크기가 커질수록 정사각형의 내부 부분은 이미 확인되었으므로 각 정사각형의 아래쪽과 오른쪽만 확인하면 됩니다. 따라서 첫 번째 반복(4개의 영역)에서는 b 셀을 확인합니다. 다음 iteration(9개 영역)에서는 c셀 등을 확인하는 식으로 진행됩니다.

함수 코드는 다음과 같습니다.

def find_square_from_point(matrix, x: int, y: int, max_side: int) -> int:
    side = 1
    for s in range(1, max_side):
        all_ones = True
        for i in range(s+1):
            if matrix[x+i][y+s] == 0 or matrix[x+s][y+i] == 0:
                all_ones = False
                break

        if not all_ones:
            break

        side += 1

    return side ** 2

예

$ ./ch-1.py "[[1, 0, 1, 0, 0],[1, 0, 1, 1, 1],[1, 1, 1, 1, 1],[1, 0, 0, 1, 0]]"
4

$ ./ch-1.py "[[0, 1],[1, 0]]"
1

$ ./ch-1.py "[[0]]"
0

작업 2: 오른쪽 간격

일

@intervals 배열이 제공됩니다. 여기서 $intervals[i] = [starti, endi]이고 각 starti는 고유합니다.

간격 i에 대한 올바른 간격은 startj >= endi이고 startj가 최소화되는 간격 j입니다. 나는 j와 같을 수 있다는 점에 유의하세요.

각 간격 i에 대해 올바른 간격 인덱스 배열을 반환하는 스크립트를 작성하세요. 간격 i에 대해 올바른 간격이 없으면 인덱스 i에 -1을 넣습니다.

내 솔루션

이 작업을 위해 효과적인 솔루션이 있지만 그것이 가장 효율적이라고 확신하지는 않습니다. 각 간격마다 세 가지 변수를 설정했습니다.

1. end_i 값은 우리가 고려해야 할 끝(두 번째) 값을 저장합니다
2. lowest_j 값은 지금까지 발견된 가장 낮은 시작 값을 저장합니다(또는 찾을 수 없는 경우 None).
3. index_j 변수는 가장 낮은_j 값의 인덱스를 저장하며, 값이 없으면 -1을 저장합니다.

그런 다음 간격을 반복하는 내부 루프가 있습니다. start_j 값(간격의 첫 번째 값)이 end_i보다 크거나 같고 low_j보다 낮은 경우 low_j 및 index_j 값을 업데이트합니다.

def maximal_square(matrix: list[list[int]]) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_size = 0

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

명령줄 입력의 경우 정수 목록을 가져와 자동으로 쌍으로 연결합니다.

예

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 1:
                max_side = min(rows-row, cols-col)
                size = find_square_from_point(matrix, row, col, max_side)
                if size > maximum_size:
                    maximum_size = size

    return maximum_size

위 내용은 간격 최대화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!