Memaksimumkan selang

Cabaran Mingguan 298

Setiap minggu Mohammad S. Anwar menghantar Cabaran Mingguan, peluang untuk kita semua mencari penyelesaian kepada dua tugas mingguan. Ini cara yang bagus untuk kita semua mempraktikkan beberapa pengekodan.

Cabaran, Penyelesaian saya

Tugasan 1: Kuasa Dua Maksimum

Tugasan

Anda diberikan matriks binari m x n dengan 0 dan 1 sahaja.

Tulis skrip untuk mencari petak terbesar yang mengandungi hanya 1 dan kembalikan kawasannya.

penyelesaian saya

Fungsi utama saya bermula dengan menyemak sama ada matriks mempunyai bilangan lajur yang betul untuk setiap baris

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)

Ia kemudian melelang melalui setiap sel dalam matriks. Jika item dalam sel itu ialah 1, ia kemudian menyemak saiz segi empat sama bermula pada kedudukan itu. Pembolehubah max_side juga dikira untuk memastikan kita tidak melampaui batas. Kami menjejaki nilai maksimum_saiz dan mengembalikan yang terbesar.

    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

Fungsi find_square_from_point sangat mengecewakan untuk diperbaiki. Saya sebenarnya mempunyai beberapa langkah sebelum saya mempunyai penyelesaian yang saya gembira untuk melakukan. Logiknya agak lurus ke hadapan. Pertimbangkan segi empat sama:

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

Apabila saiz segi empat sama bertambah, saya hanya perlu menyemak bahagian bawah dan kanan setiap petak, kerana saya tahu bahagian dalam petak itu telah pun disemak. Jadi untuk lelaran pertama (kawasan empat), saya menyemak sel b. Lelaran seterusnya (luas 9), saya menyemak sel c, dan seterusnya.

Ini ialah kod fungsi:

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

Contoh

$ ./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

Tugasan 2: Selang Kanan

Tugasan

Anda diberikan tatasusunan @intervals, di mana $intervals[i] = [starti, endi] dan setiap starti adalah unik.

Selang yang betul untuk selang i ialah selang j supaya startj >= endi dan startj diminimumkan. Sila ambil perhatian bahawa saya mungkin sama dengan j.

Tulis skrip untuk mengembalikan tatasusunan indeks selang yang betul untuk setiap selang i. Jika tiada selang tepat wujud untuk selang i, maka letakkan -1 pada indeks i.

penyelesaian saya

Untuk tugasan ini, saya mempunyai penyelesaian yang berkesan, tetapi saya tidak yakin ia adalah yang paling berkesan. Untuk setiap selang, saya menetapkan tiga pembolehubah:

1. Nilai end_i menyimpan nilai akhir (kedua) yang perlu kita pertimbangkan
2. Nilai lowest_j menyimpan nilai permulaan terendah yang ditemui setakat ini (atau Tiada jika tidak ditemui).
3. Pembolehubah index_j menyimpan indeks bagi nilai_j terendah, atau -1 jika tidak ditemui.

Saya kemudian mempunyai gelung dalam yang berulang sepanjang selang waktu. Jika nilai start_j (nilai pertama dalam selang) lebih besar daripada atau sama dengan end_i dan lebih rendah daripada lowest_j, saya mengemas kini nilai lowest_j dan 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)

Untuk input daripada baris arahan, saya mengambil senarai integer dan memasangkannya secara automatik.

Contoh

    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

Atas ialah kandungan terperinci Memaksimumkan selang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!