Matriks Lingkaran IV

2326. Matriks Lingkaran IV

Kesukaran: Sederhana

Topik: Tatasusunan, Senarai Terpaut, Matriks, Simulasi

Anda diberi dua integer m dan n, yang mewakili dimensi matriks.

Anda juga diberikan ketua senarai integer yang dipautkan.

Janakan matriks m x n yang mengandungi integer dalam senarai terpaut yang dibentangkan dalam urutan spiral (ikut arah jam), bermula dari kiri atas matriks . Jika masih ada ruang kosong, isikan dengan -1.

Kembalikan matriks yang dijana.

Contoh 1:

• Input: m = 3, n = 5, kepala = [3,0,2,6,8,1,7,9,4,2,5,5,0]
• Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
• Penjelasan:
  • Rajah di atas menunjukkan cara nilai dicetak dalam matriks.
  • Perhatikan bahawa ruang yang tinggal dalam matriks diisi dengan -1.

Contoh 2:

• Input: m = 1, n = 4, kepala = [0,1,2]
• Output: [[0,1,2,-1]]
• Penjelasan:
  • Rajah di atas menunjukkan cara nilai dicetak dari kiri ke kanan dalam matriks.
  • Ruang terakhir dalam matriks ditetapkan kepada -1.

Contoh 3:

• Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Output: 10

Kekangan:

• 1 <= m, n <= 10⁵
• 1 <= m, n <= 10⁵
• Bilangan nod dalam senarai berada dalam julat [1, m * n].
• 0 <= Node.val <= 1000

Petunjuk:

1. Pertama, hasilkan matriks m x n yang diisi dengan -1s.
2. Navigasi dalam matriks di (i, j) dengan bantuan vektor arah ⟨di, dj⟩. Di (i, j), anda perlu memutuskan sama ada anda boleh meneruskan ke arah semasa.
3. Jika anda tidak dapat meneruskan, putar arah vektor mengikut arah jam sebanyak 90 darjah.

Penyelesaian:

Kami akan mensimulasikan traversal lingkaran bagi matriks m x n, mengisinya dengan nilai daripada senarai terpaut. Kedudukan selebihnya yang tidak mempunyai nilai senarai terpaut yang sepadan akan diisi dengan -1.

Begini cara penyelesaiannya distrukturkan:

1. Permulaan Matriks: Kami mula-mula mencipta matriks m x n yang dimulakan dengan -1.
2. Vektor Arah: Pergerakan lingkaran boleh dikawal menggunakan vektor arah yang berkitar melalui arah kanan, bawah, kiri dan atas. Ini memastikan bahawa kami merentasi matriks secara berpilin.
3. Lelaran Senarai Terpaut: Kami merentasi senarai terpaut, meletakkan nilai dalam matriks dalam susunan lingkaran.
4. Pengendalian Sempadan: Kami menyemak sama ada kami telah sampai ke sempadan atau menemui sel yang sudah diisi. Jika ya, kami menukar arah (mengikut arah jam).

Mari laksanakan penyelesaian ini dalam PHP: 2326. Matriks Lingkaran IV

val = $val;
        $this->next = $next;
    }
}
/**
 * @param Integer $m
 * @param Integer $n
 * @param ListNode $head
 * @return Integer[][]
 */
function spiralMatrix($m, $n, $head) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to print the matrix (for debugging)
function printMatrix($matrix) {
    foreach ($matrix as $row) {
        echo implode(" ", $row) . "\n";
    }
}

// Example usage:
// Create the linked list: [3,0,2,6,8,1,7,9,4,2,5,5,0]
$head = new ListNode(3);
$head->next = new ListNode(0);
$head->next->next = new ListNode(2);
$head->next->next->next = new ListNode(6);
$head->next->next->next->next = new ListNode(8);
$head->next->next->next->next->next = new ListNode(1);
$head->next->next->next->next->next->next = new ListNode(7);
$head->next->next->next->next->next->next->next = new ListNode(9);
$head->next->next->next->next->next->next->next->next = new ListNode(4);
$head->next->next->next->next->next->next->next->next->next = new ListNode(2);
$head->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next->next = new ListNode(0);

$m = 3;
$n = 5;

$matrix = spiralMatrix($m, $n, $head);
printMatrix($matrix);
?>





  
  
  Penjelasan:



Permulaan Matriks: Matriks dimulakan dengan -1 supaya mana-mana ruang yang tidak diisi akan kekal -1 secara lalai.

Pergerakan Lingkaran:


Dirs vektor arah mengurus pergerakan dalam empat arah: kanan, bawah, kiri dan atas.
Indeks dirIndex menjejaki arah semasa. Selepas bergerak ke satu arah, kami mengira kedudukan seterusnya dan menyemak sama ada ia sah. Jika tidak, kita tukar haluan.



Lintasan Senarai Terpaut:


Kami merentasi nod senarai terpaut, meletakkan nilai dalam matriks satu demi satu, mengikut susunan lingkaran.



Perubahan Sempadan dan Hala Tuju:


Apabila kami menghadapi kedudukan yang tidak sah (di luar sempadan atau sudah diisi), kami memutarkan arah sebanyak 90 darjah (iaitu, menukar vektor arah).





  
  
  Kerumitan Masa:



Pengisian matriks mengambil masa O(m * n) kerana kami merentasi setiap sel sekali. Oleh itu, kerumitan masa ialah O(m * n), yang cekap memandangkan kekangan.


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 Matriks Lingkaran IV. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!