Maximiser l'intervalle

Défi hebdomadaire 298

Chaque semaine, Mohammad S. Anwar envoie The Weekly Challenge, une chance pour nous tous de trouver des solutions à deux tâches hebdomadaires. C'est une excellente façon pour nous tous de pratiquer le codage.

Défi, Mes solutions

Tâche 1 : Carré maximal

Tâche

Vous recevez une matrice binaire m x n avec 0 et 1 seulement.

Écrivez un script pour trouver le plus grand carré contenant uniquement des 1 et renvoyer son aire.

Ma solution

Ma fonction principale commence par vérifier que la matrice a le bon nombre de colonnes pour chaque ligne

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)

Il parcourt ensuite chaque cellule de la matrice. Si l'élément dans cette cellule est un 1, il vérifie alors la taille du carré à partir de cette position. La variable max_side est également calculée pour garantir que nous ne sortons pas des limites. Nous gardons une trace de la valeur maximum_size et renvoyons la plus grande.

    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

La fonction find_square_from_point était frustrante à réussir. En fait, j'ai fait quelques essais avant d'avoir une solution que j'étais heureux de m'engager. La logique est assez simple. Considérez le carré :

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

À mesure que la taille du carré augmente, il me suffit de vérifier le bas et le côté droit de chaque carré, car je sais que la partie intérieure du carré a déjà été vérifiée. Donc pour la première itération (une surface de quatre), je vérifie les cellules b. A l'itération suivante (zone de 9), je vérifie les cellules c, et ainsi de suite.

Voici le code de la fonction :

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

Exemples

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

Tâche 2 : intervalle correct

Tâche

Vous recevez un tableau de @intervals, où $intervals[i] = [starti, endi] et chaque starti est unique.

Le bon intervalle pour un intervalle i est un intervalle j tel que startj >= endi et startj est minimisé. Veuillez noter que je peux égaler j.

Écrivez un script pour renvoyer un tableau d'indices d'intervalle droits pour chaque intervalle i. Si aucun intervalle droit n'existe pour l'intervalle i, alors mettez -1 à l'index i.

Ma solution

Pour cette tâche, j'ai une solution qui fonctionne, mais je ne suis pas convaincu qu'elle soit la plus efficace. Pour chaque intervalle, j'ai défini trois variables :

1. La valeur end_i stocke la valeur de fin (deuxième) que nous devons prendre en compte
2. La valeur lower_j stocke la valeur de départ la plus basse trouvée jusqu'à présent (ou Aucune si elle n'est pas trouvée).
3. La variable index_j stocke l'index de la valeur_j la plus basse, ou -1 si elle n'est pas trouvée.

J'ai alors une boucle interne qui itère sur les intervalles. Si la valeur start_j (première valeur de l'intervalle) est supérieure ou égale à end_i et est inférieure à lower_j, je mets à jour les valeurs lower_j et 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)

Pour les entrées de la ligne de commande, je prends une liste d'entiers et je les associe automatiquement.

Exemples

    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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!