Maximierung des Intervalls

Wöchentliche Herausforderung 298

Jede Woche verschickt Mohammad S. Anwar die Weekly Challenge, eine Chance für uns alle, Lösungen für zwei wöchentliche Aufgaben zu finden. Es ist eine großartige Möglichkeit für uns alle, etwas Programmieren zu üben.

Herausforderung, meine Lösungen

Aufgabe 1: Maximales Quadrat

Aufgabe

Sie erhalten eine m x n-Binärmatrix mit nur 0 und 1.

Schreiben Sie ein Skript, um das größte Quadrat zu finden, das nur Einsen enthält, und geben Sie dessen Fläche zurück.

Meine Lösung

Meine Hauptfunktion beginnt mit der Überprüfung, ob die Matrix für jede Zeile die richtige Anzahl von Spalten hat

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)

Es durchläuft dann jede Zelle in der Matrix. Wenn das Element in dieser Zelle eine 1 ist, wird die Größe des Quadrats ab dieser Position überprüft. Die Variable max_side wird ebenfalls berechnet, um sicherzustellen, dass wir die Grenzen nicht überschreiten. Wir verfolgen den Wert „maximum_size“ und geben den größten Wert zurück.

    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

Es war frustrierend, die Funktion find_square_from_point richtig zu machen. Ich hatte tatsächlich ein paar Versuche, bis ich eine Lösung gefunden hatte, die ich gerne anwendete. Die Logik ist ziemlich einfach. Betrachten Sie das Quadrat:

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

Wenn das Quadrat größer wird, muss ich nur die Unterseite und die rechte Seite jedes Quadrats überprüfen, da ich weiß, dass der innere Teil des Quadrats bereits überprüft wurde. Für die erste Iteration (eine Fläche von vier) überprüfe ich also die B-Zellen. Bei der nächsten Iteration (Bereich von 9) überprüfe ich die c-Zellen und so weiter.

Dies ist der Code der Funktion:

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

Beispiele

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

Aufgabe 2: Richtiges Intervall

Aufgabe

Sie erhalten ein Array von @intervals, wobei $intervals[i] = [starti, endi] und jedes starti einzigartig ist.

Das richtige Intervall für ein Intervall i ist ein Intervall j, so dass startj >= endi und startj minimiert ist. Bitte beachten Sie, dass ich j.

entsprechen kann

Schreiben Sie ein Skript, um für jedes Intervall i ein Array rechter Intervallindizes zurückzugeben. Wenn für Intervall i kein richtiges Intervall existiert, dann setze -1 am Index i.

Meine Lösung

Für diese Aufgabe habe ich eine Lösung, die funktioniert, aber ich bin nicht davon überzeugt, dass sie die effizienteste ist. Für jedes Intervall lege ich drei Variablen fest:

1. Der end_i-Wert speichert den Endwert (zweiten Wert), den wir berücksichtigen müssen
2. Der Wert lowest_j speichert den niedrigsten bisher gefundenen Startwert (oder None, wenn nicht gefunden).
3. Die Variable index_j speichert den Index des niedrigsten_j-Werts oder -1, wenn er nicht gefunden wird.

Ich habe dann eine innere Schleife, die über die Intervalle iteriert. Wenn der Wert „start_j“ (erster Wert im Intervall) größer oder gleich „end_i“ und kleiner als „lowest_j“ ist, aktualisiere ich die Werte „lowest_j“ und „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)

Für Eingaben über die Befehlszeile nehme ich eine Liste von Ganzzahlen und ordne sie automatisch zu Paaren.

Beispiele

    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

Das obige ist der detaillierte Inhalt vonMaximierung des Intervalls. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!