Kira Submatriks Square dengan Semua Satu

1277. Kira Submatriks Square dengan Semua Satu

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik, Matriks

Diberikan m * n matriks satu dan sifar, kembalikan berapa banyak persegi submatriks mempunyai semua satu.

Contoh 1:

• Input: matriks = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
• Output: 15
• Penjelasan:
  • Terdapat 10 segi empat sama sisi 1.
  • Terdapat 4 segi empat sama sisi 2.
  • Terdapat 1 segi empat sama sisi 3.
  • Jumlah bilangan petak = 10 4 1 = 15.

Contoh 2:

• Input: matriks = [[1,0,1], [1,1,0], [1,1,0]]
• Output: 7
• Penjelasan:
  • Terdapat 6 segi empat sama sisi 1.
  • Terdapat 1 segi empat sama sisi 2.
  • Jumlah bilangan petak = 6 1 = 7.

Kekangan:

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

Petunjuk:

1. Buat jadual tambahan yang mengira jumlah elemen submatriks dengan sudut atas pada (0,0).
2. Gelung pada semua subpetak dalam O(n³) dan semak sama ada jumlah itu menjadikan keseluruhan tatasusunan menjadi satu, jika ia menandakan kemudian tambah 1 pada jawapan.

Penyelesaian:

Kita boleh menggunakan Pengaturcaraan Dinamik (DP) untuk menjejaki bilangan submatriks segi empat sama dengan semua yang boleh berakhir pada setiap sel dalam matriks. Inilah pendekatan untuk mencapai matlamat ini:

1. Definisi Matriks DP:

   • Tentukan dp matriks DP dengan dp[i][j] mewakili saiz submatriks segi empat sama terbesar dengan semua submatriks segi empat sama yang mempunyai sudut kanan bawahnya di sel (i, j).

2. Formula Peralihan:

   • Untuk setiap sel (i, j) dalam matriks:

     • Jika matriks[i][j] ialah 1, nilai dp[i][j] bergantung kepada minimum segi empat sama yang boleh dibentuk dengan melanjutkan daripada (i-1, j), (i, j -1), dan (i-1, j-1). Formula peralihan ialah:

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

     Salin selepas log masuk

     Salin selepas log masuk

  - 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. Kira Semua Petak:

   • Kumpulkan nilai dp[i][j] untuk semua (i, j) untuk mendapatkan jumlah bilangan segi empat sama semua saiz.

2. Kerumitan Masa:

   • Penyelesaian berfungsi dalam O(m X n), di mana m dan n ialah dimensi matriks.

Mari laksanakan penyelesaian ini dalam PHP: 1277. Kira Submatriks Square dengan Semua Satu

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

Penjelasan:

1. Kami memulakan dp tatasusunan 2D untuk menjejaki saiz submatriks persegi terbesar yang berakhir pada setiap kedudukan (i, j).
2. Untuk setiap sel dalam matriks:
   • Jika sel mempunyai 1, kami mengira dp[i][j] berdasarkan sel jiran dan menambah nilainya kepada totalSquares.
3. Akhir sekali, totalSquares mengandungi kiraan semua submatriks segi empat sama dengan kesemuanya.

Penyelesaian ini cekap dan memenuhi kekangan yang disediakan dalam masalah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Kira Submatriks Square dengan Semua Satu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!