Compter les sous-matrices carrées avec tous les uns

1277. Compter les sous-matrices carrées avec tous les uns

Difficulté :Moyen

Sujets :Array, Programmation dynamique, Matrice

Étant donné une matrice m * n de uns et de zéros, renvoie combien de carrés sous-matrices ont toutes des uns.

Exemple 1 :

• Entrée : matrice = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
• Sortie : 15
• Explication :
  • Il y a 10 carrés du côté 1.
  • Il y a 4 carrés du côté 2.
  • Il y a 1 carré du côté 3.
  • Nombre total de carrés = 10 4 1 = 15.

Exemple 2 :

• Entrée : matrice = [[1,0,1], [1,1,0], [1,1,0]]
• Sortie :7
• Explication :
  • Il y a 6 carrés de côté 1.
  • Il y a 1 carré de côté 2.
  • Nombre total de carrés = 6 1 = 7.

Contraintes :

• 1 <= longueur arr. <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Indice :

1. Créez un tableau additif qui compte la somme des éléments de la sous-matrice avec le coin supérieur à (0,0).
2. Faites une boucle sur tous les sous-carrés dans O(n³) et vérifiez si la somme fait que tout le tableau soit un, si cela est vérifié, ajoutez 1 à la réponse.

Solution :

Nous pouvons utiliser la Programmation dynamique (DP) pour garder une trace du nombre de sous-matrices carrées avec toutes celles qui peuvent se terminer à chaque cellule de la matrice. Voici la démarche pour y parvenir :

1. Définition de la matrice DP :

   • Définissez une matrice DP dp où dp[i][j] représente la taille de la plus grande sous-matrice carrée avec toutes celles qui ont son coin inférieur droit dans la cellule (i, j).

2. Formule de transition :

   • Pour chaque cellule (i, j) de la matrice :

     • Si matrice[i][j] vaut 1, la valeur de dp[i][j] dépend du minimum des carrés pouvant être formés en étendant depuis (i-1, j), (i, j -1), et (i-1, j-1). La formule de transition est :

     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     

  - If `matrix[i][j]` is 0, `dp[i][j]` will be 0 because a square of ones cannot end at a cell with a zero.

1. Compter tous les carrés :

   • Accumulez les valeurs de dp[i][j] pour tout (i, j) pour obtenir le nombre total de carrés de toutes tailles.

2. Complexité temporelle :

   • La solution fonctionne en O(m X n), où m et n sont les dimensions de la matrice.

Implémentons cette solution en PHP : 1277. Compter les sous-matrices carrées avec tous les uns

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Explication:

1. Nous initialisons un tableau 2D dp pour garder une trace de la taille de la plus grande sous-matrice carrée se terminant à chaque position (i, j).
2. Pour chaque cellule de la matrice :
   • Si la cellule a un 1, nous calculons dp[i][j] en fonction des cellules voisines et ajoutons sa valeur à totalSquares.
3. Enfin, totalSquares contient le nombre de toutes les sous-matrices carrées avec toutes des uns.

Cette solution est efficace et répond aux contraintes fournies dans le problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

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!