Balik Lajur Untuk Bilangan Maksimum Baris Sama

1072. Balik Lajur Untuk Bilangan Maksimum Baris Sama

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Matriks

Anda diberi matriks matriks binari m x n.

Anda boleh memilih sebarang bilangan lajur dalam matriks dan menyelak setiap sel dalam lajur itu (iaitu, Tukar nilai sel daripada 0 kepada 1 atau sebaliknya).

Kembali bilangan maksimum baris yang mempunyai semua nilai sama selepas beberapa bilangan selak.

Contoh 1:

• Input: matriks = [[0,1],[1,1]]
• Output: 1
• Penjelasan: Selepas membalikkan tiada nilai, 1 baris mempunyai semua nilai yang sama.

Contoh 2:

• Input: matriks = [[0,1],[1,0]]
• Output: 2
• Penjelasan: Selepas membalikkan nilai dalam lajur pertama, kedua-dua baris mempunyai nilai yang sama.

Contoh 3:

• Input: matriks = [[0,0,0],[0,0,1],[1,1,0]]
• Output: 2
• Penjelasan: Selepas membalikkan nilai dalam dua lajur pertama, dua baris terakhir mempunyai nilai yang sama.

Kekangan:

• m == matriks.panjang
• n == matriks[i].panjang
• 1 <= m, n <= 300
• matriks[i][j] ialah sama ada 0 atau 1.

Petunjuk:

1. Membalikkan subset lajur adalah seperti melakukan XOR bitwise bagi beberapa nombor K pada setiap baris. Kami mahu baris X dengan X ^ K = semua 0s atau semua 1s. Ini adalah sama dengan X = X^K ^K = (semua 0s atau semua 1s) ^ K, jadi kita mahu mengira baris yang mempunyai set bit bertentangan. Contohnya, jika K = 1, maka kita mengira baris X = (00000...001, atau 1111....110).

Penyelesaian:

Kami boleh menggunakan peta cincang untuk mengumpulkan baris yang boleh dibuat serupa dengan membalikkan lajur tertentu. Baris yang boleh dibuat sama mempunyai sama ada corak yang sama atau corak pelengkap (penafian bitwise).

Berikut ialah penyelesaian langkah demi langkah:

Algoritma:

1. Untuk setiap baris, hitung corak dan corak pelengkapnya:
   • Coraknya ialah barisan seperti sedia ada.
   • Corak pelengkap ialah hasil daripada membalikkan semua bit dalam baris.
2. Gunakan peta cincang untuk mengira kejadian corak dan pelengkapnya.
3. Bilangan maksimum untuk mana-mana corak tunggal atau pelengkapnya memberikan hasil.

Mari laksanakan penyelesaian ini dalam PHP: 1072. Balik Lajur Untuk Bilangan Maksimum Baris Sama

  
  
  Penjelasan:




Corak dan Pelengkap:


Untuk setiap baris, coraknya ialah baris bercantum (mis., 010).
Pelengkap membalikkan semua bit baris (mis., 101).



Peta Hash: Kira kejadian setiap corak dan pelengkapnya. Ini membantu kumpulan baris yang boleh dibuat serupa.

Kiraan Maks: Cari kiraan maksimum bagi satu corak atau pelengkapnya untuk menentukan bilangan baris yang boleh dibuat sama.



  
  
  Kerumitan:




Kerumitan Masa: O(m x n), dengan m ialah bilangan baris dan n ialah bilangan lajur.

Kerumitan Angkasa: O(m x n), untuk menyimpan corak dalam peta cincang.


Penyelesaian ini mematuhi kekangan dan cekap untuk saiz 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 Balik Lajur Untuk Bilangan Maksimum Baris Sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!