Rumah pembangunan bahagian belakang tutorial php . Cari negeri selamat akhirnya

. Cari negeri selamat akhirnya

Jan 25, 2025 am 06:04 AM

802. Cari Keadaan Selamat Akhirnya

Kesukaran: Sederhana

Topik: Carian Pertama Kedalaman, Carian Luas-Pertama, Graf, Isih Topologi

Terdapat graf terarah bagi n nod dengan setiap nod dilabelkan dari 0 hingga n - 1. Graf diwakili oleh 0-diindeks graf tatasusunan integer 2D dengan graf[i] ialah tatasusunan integer daripada nod bersebelahan dengan nod i, bermakna terdapat tepi dari nod i ke setiap nod dalam graf[i].

Nod ialah nod terminal jika tiada tepi keluar. Nod ialah nod selamat jika setiap laluan yang mungkin bermula dari nod itu menuju ke nod terminal (atau nod selamat yang lain).

Kembalikan tatasusunan yang mengandungi semua nod selamat graf. Jawapan hendaklah disusun mengikut urutan menaik.

Contoh 1:

. Cari negeri selamat akhirnya

  • Input: graf = [[1,2],[2,3],[5],[0],[5],[],[]]
  • Output: [2,4,5,6]
  • Penjelasan: Graf yang diberikan ditunjukkan di atas. Nod 5 dan 6 ialah nod terminal kerana tiada tepi keluar daripada salah satu daripadanya. Setiap laluan bermula pada nod 2, 4, 5 dan 6 semuanya menuju ke nod 5 atau 6.

Contoh 2:

  • Input: graf = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
  • Output: [4]
  • Penjelasan: Hanya nod 4 ialah nod terminal dan setiap laluan bermula pada nod 4 menuju ke nod 4.

Kekangan:

  • n == graf.panjang
  • 1 4
  • 0
  • 0
  • graf[i] diisih dalam susunan yang semakin meningkat.
  • Graf mungkin mengandungi gelung kendiri.
  • Bilangan tepi dalam graf akan berada dalam julat [1, 4 * 104].

Penyelesaian:

Kami perlu mengenal pasti semua nod selamat dalam graf. Ini melibatkan pemeriksaan jika bermula dari nod tertentu, setiap laluan akhirnya mencapai nod terminal atau nod selamat yang lain. Penyelesaiannya menggunakan Depth-First Search (DFS) untuk mengesan kitaran dan mengklasifikasikan nod sebagai selamat atau tidak selamat.

Wawasan Utama:

  1. nod terminal : nod tanpa tepi keluar adalah nod terminal.
  2. nod selamat : Node selamat jika, bermula dari nod itu, semua jalan akhirnya membawa kepada nod terminal atau nod selamat lain.
  3. Pengesanan kitaran : Jika nod adalah sebahagian daripada kitaran, ia bukan nod yang selamat kerana laluan bermula daripadanya tidak akan membawa kepada nod terminal.

Pendekatan:

  • Kami menggunakan DFS untuk meneroka setiap nod dan menentukan sama ada ia adalah sebahagian daripada kitaran. Nod yang merupakan sebahagian daripada kitaran atau membawa kepada kitaran ditandakan tidak selamat.
  • nod yang akhirnya membawa kepada nod terminal atau nod selamat lain ditandakan selamat.

kami menggunakan array yang dikunjungi dengan tiga negeri:

  • 0: Node belum dikunjungi.
  • 1: Node sedang dikunjungi (iaitu, dalam timbunan rekursi).
  • 2: Nod telah diproses sepenuhnya dan selamat.

Langkah:

  1. melakukan DFS untuk setiap nod.
  2. Gunakan negeri -negeri yang dikunjungi untuk menandakan nod selamat/tidak selamat.
  3. Kumpulkan semua nod yang selamat.

mari kita melaksanakan penyelesaian ini dalam php: 802. Cari negeri selamat akhirnya

<?php /**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>
Salin selepas log masuk
Salin selepas log masuk

Penjelasan:

  1. fungsi DFS :

    • Fungsi DFS melakukan carian mendalam pada nod, menandakannya sebagai "melawat" (1) apabila ia bermula dan "selamat" (2) apabila semua jirannya selamat.
    • Jika mana -mana jirannya membawa kepada kitaran (ditunjukkan oleh DFS ($ jiran) == 1), nod ditandakan tidak selamat (1).
    • Jika semua jiran membawa kepada nod terminal atau nod selamat, ia ditandakan sebagai selamat (2).
  2. Fungsi utama :

      kita meleleh melalui semua nod dan gunakan DFS untuk memeriksa sama ada setiap nod selamat atau tidak.
    • semua nod selamat dikumpulkan dalam array $ Safenodes dan dikembalikan.
Contoh Walkthrough:

Contoh 1:

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));
Salin selepas log masuk
    Dalam contoh ini, nod 5 dan 6 adalah nod terminal (tiada tepi keluar).
  • node 4 membawa kepada nod 5, jadi ia juga selamat.
  • nod 2 membawa kepada nod 5, jadi selamat.
  • nod 1 dan 0 akhirnya membawa kepada kitaran atau nod yang tidak selamat, jadi mereka tidak selamat.

output:

[2, 4, 5, 6]
Salin selepas log masuk
Contoh 2:

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));
Salin selepas log masuk
    Dalam contoh ini, hanya node 4 adalah nod terminal, dan semua laluan bermula dari nod 4 membawa kepada nod 4.
  • semua nod lain akhirnya membawa kepada kitaran atau nod yang tidak selamat.

output:

<?php /**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>
Salin selepas log masuk
Salin selepas log masuk

Kerumitan Masa dan Ruang:

  • Kerumitan Masa: O(n e), dengan n ialah bilangan nod dan e ialah bilangan tepi. Kami melawati setiap nod sekali dan memproses setiap tepi sekali.
  • Kerumitan Angkasa: O(n) untuk tatasusunan yang dilawati dan timbunan ulangan.

Penyelesaian ini dengan cekap menentukan nod selamat menggunakan DFS, memastikan kekangan masalah dipenuhi.

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 . Cari negeri selamat akhirnya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Tutorial Java
1655
14
Tutorial PHP
1252
29
Tutorial C#
1226
24
Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Apr 05, 2025 am 12:04 AM

JWT adalah standard terbuka berdasarkan JSON, yang digunakan untuk menghantar maklumat secara selamat antara pihak, terutamanya untuk pengesahan identiti dan pertukaran maklumat. 1. JWT terdiri daripada tiga bahagian: header, muatan dan tandatangan. 2. Prinsip kerja JWT termasuk tiga langkah: menjana JWT, mengesahkan JWT dan muatan parsing. 3. Apabila menggunakan JWT untuk pengesahan di PHP, JWT boleh dijana dan disahkan, dan peranan pengguna dan maklumat kebenaran boleh dimasukkan dalam penggunaan lanjutan. 4. Kesilapan umum termasuk kegagalan pengesahan tandatangan, tamat tempoh, dan muatan besar. Kemahiran penyahpepijatan termasuk menggunakan alat debugging dan pembalakan. 5. Pengoptimuman prestasi dan amalan terbaik termasuk menggunakan algoritma tandatangan yang sesuai, menetapkan tempoh kesahihan dengan munasabah,

Bagaimanakah sesi merampas kerja dan bagaimana anda dapat mengurangkannya dalam PHP? Bagaimanakah sesi merampas kerja dan bagaimana anda dapat mengurangkannya dalam PHP? Apr 06, 2025 am 12:02 AM

Sesi rampasan boleh dicapai melalui langkah -langkah berikut: 1. Dapatkan ID Sesi, 2. Gunakan ID Sesi, 3. Simpan sesi aktif. Kaedah untuk mengelakkan rampasan sesi dalam PHP termasuk: 1. Gunakan fungsi Sesi_Regenerate_ID () untuk menjana semula ID Sesi, 2. Data sesi stor melalui pangkalan data, 3.

Apakah Prinsip Reka Bentuk API REST? Apakah Prinsip Reka Bentuk API REST? Apr 04, 2025 am 12:01 AM

Prinsip reka bentuk Restapi termasuk definisi sumber, reka bentuk URI, penggunaan kaedah HTTP, penggunaan kod status, kawalan versi, dan benci. 1. Sumber harus diwakili oleh kata nama dan dikekalkan pada hierarki. 2. Kaedah HTTP harus mematuhi semantik mereka, seperti GET digunakan untuk mendapatkan sumber. 3. Kod status hendaklah digunakan dengan betul, seperti 404 bermakna sumber tidak wujud. 4. Kawalan versi boleh dilaksanakan melalui URI atau header. 5. Boots Operasi Pelanggan Hateoas melalui pautan sebagai tindak balas.

Apakah kelas tanpa nama di PHP dan kapan anda boleh menggunakannya? Apakah kelas tanpa nama di PHP dan kapan anda boleh menggunakannya? Apr 04, 2025 am 12:02 AM

Fungsi utama kelas tanpa nama dalam PHP adalah untuk membuat objek satu kali. 1. Kelas tanpa nama membenarkan kelas tanpa nama ditakrifkan secara langsung dalam kod, yang sesuai untuk keperluan sementara. 2. Mereka boleh mewarisi kelas atau melaksanakan antara muka untuk meningkatkan fleksibiliti. 3. Beri perhatian kepada prestasi dan kebolehbacaan kod apabila menggunakannya, dan elakkan berulang kali menentukan kelas tanpa nama yang sama.

Bagaimanakah anda mengendalikan pengecualian dengan berkesan dalam PHP (cuba, menangkap, akhirnya, membuang)? Bagaimanakah anda mengendalikan pengecualian dengan berkesan dalam PHP (cuba, menangkap, akhirnya, membuang)? Apr 05, 2025 am 12:03 AM

Dalam PHP, pengendalian pengecualian dicapai melalui percubaan, menangkap, akhirnya, dan membuang kata kunci. 1) blok percubaan mengelilingi kod yang boleh membuang pengecualian; 2) Blok tangkapan mengendalikan pengecualian; 3) Akhirnya Blok memastikan bahawa kod itu sentiasa dilaksanakan; 4) Lemparan digunakan untuk membuang pengecualian secara manual. Mekanisme ini membantu meningkatkan keteguhan dan mengekalkan kod anda.

Apakah perbezaan antara termasuk, memerlukan, termasuk_once, memerlukan_once? Apakah perbezaan antara termasuk, memerlukan, termasuk_once, memerlukan_once? Apr 05, 2025 am 12:07 AM

Dalam PHP, perbezaan antara termasuk, memerlukan, termasuk_once, memerlukan_once adalah: 1) termasuk menghasilkan amaran dan terus melaksanakan, 2) memerlukan menghasilkan ralat maut dan berhenti pelaksanaan, 3) termasuk_once dan memerlukan_once mencegah kemasukan berulang. Pilihan fungsi ini bergantung kepada kepentingan fail dan sama ada perlu untuk mencegah kemasukan pendua. Penggunaan rasional dapat meningkatkan kebolehbacaan dan pemeliharaan kod.

Terangkan jenis ralat yang berbeza dalam PHP (notis, amaran, ralat maut, ralat parse). Terangkan jenis ralat yang berbeza dalam PHP (notis, amaran, ralat maut, ralat parse). Apr 08, 2025 am 12:03 AM

Terdapat empat jenis kesilapan utama dalam PHP: 1.Notice: yang paling sedikit, tidak akan mengganggu program, seperti mengakses pembolehubah yang tidak ditentukan; 2. Amaran: Serius daripada notis, tidak akan menamatkan program, seperti tidak mengandungi fail; 3. FatalError: Yang paling serius, akan menamatkan program ini, seperti tidak memanggil fungsi; 4. ParseError: Kesalahan sintaks, akan menghalang program daripada dilaksanakan, seperti lupa untuk menambah tag akhir.

PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular Apr 14, 2025 am 12:13 AM

PHP dan Python masing -masing mempunyai kelebihan mereka sendiri, dan memilih mengikut keperluan projek. 1.PHP sesuai untuk pembangunan web, terutamanya untuk pembangunan pesat dan penyelenggaraan laman web. 2. Python sesuai untuk sains data, pembelajaran mesin dan kecerdasan buatan, dengan sintaks ringkas dan sesuai untuk pemula.

See all articles