間隔を最大化する

ウィークリーチャレンジ 298

Mohammad S. Anwar は毎週、毎週 2 つのタスクに対する解決策を全員が考え出すチャンスであるウィークリー チャレンジを送信します。これは、私たち全員がコーディングを練習するのに最適な方法です。

挑戦、私の解決策

タスク 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 セルをチェックします。次の反復 (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 です。 i が j に等しい可能性があることに注意してください。

各間隔 i の正しい間隔インデックスの配列を返すスクリプトを作成します。間隔 i に適切な間隔が存在しない場合は、インデックス i に -1 を置きます。

私の解決策

このタスクに関しては、有効な解決策がありますが、それが最も効率的であるとは確信できません。間隔ごとに、次の 3 つの変数を設定します。

1. end_i 値には、考慮する必要がある終了 (2 番目) の値が格納されます
2. 値 lower_j には、これまでに見つかった最小の開始値 (見つからない場合は None) が格納されます。
3. index_j 変数には、最小の_j 値のインデックスが格納されます。見つからない場合は -1 が格納されます。

次に、間隔を反復する内部ループを作成します。 start_j 値 (間隔内の最初の値) が end_i 以上で、most_j より小さい場合、most_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 中国語 Web サイトの他の関連記事を参照してください。