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!

Artikel Panas

<🎜>: Bubble Gum Simulator Infinity - Cara Mendapatkan dan Menggunakan Kekunci Diraja
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Sistem Fusion, dijelaskan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Cara Membuka Kunci Cangkuk Bergelut
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

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
1673
14
Tutorial PHP
1278
29
Tutorial C#
1257
24
Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Apr 17, 2025 am 12:06 AM

Dalam php, kata laluan_hash dan kata laluan 1) password_hash menjana hash yang mengandungi nilai garam untuk meningkatkan keselamatan. 2) Kata Laluan_verify Sahkan kata laluan dan pastikan keselamatan dengan membandingkan nilai hash. 3) MD5 dan SHA1 terdedah dan kekurangan nilai garam, dan tidak sesuai untuk keselamatan kata laluan moden.

Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Apr 17, 2025 am 12:25 AM

Jenis PHP meminta untuk meningkatkan kualiti kod dan kebolehbacaan. 1) Petua Jenis Skalar: Oleh kerana Php7.0, jenis data asas dibenarkan untuk ditentukan dalam parameter fungsi, seperti INT, Float, dan lain -lain. 2) Return Type Prompt: Pastikan konsistensi jenis nilai pulangan fungsi. 3) Jenis Kesatuan Prompt: Oleh kerana Php8.0, pelbagai jenis dibenarkan untuk ditentukan dalam parameter fungsi atau nilai pulangan. 4) Prompt jenis yang boleh dibatalkan: membolehkan untuk memasukkan nilai null dan mengendalikan fungsi yang boleh mengembalikan nilai null.

PHP dan Python: Paradigma yang berbeza dijelaskan PHP dan Python: Paradigma yang berbeza dijelaskan Apr 18, 2025 am 12:26 AM

PHP terutamanya pengaturcaraan prosedur, tetapi juga menyokong pengaturcaraan berorientasikan objek (OOP); Python menyokong pelbagai paradigma, termasuk pengaturcaraan OOP, fungsional dan prosedur. PHP sesuai untuk pembangunan web, dan Python sesuai untuk pelbagai aplikasi seperti analisis data dan pembelajaran mesin.

Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Apr 15, 2025 am 12:15 AM

Menggunakan penyataan preprocessing dan PDO dalam PHP secara berkesan dapat mencegah serangan suntikan SQL. 1) Gunakan PDO untuk menyambung ke pangkalan data dan tetapkan mod ralat. 2) Buat kenyataan pra -proses melalui kaedah menyediakan dan lulus data menggunakan ruang letak dan laksanakan kaedah. 3) Hasil pertanyaan proses dan pastikan keselamatan dan prestasi kod.

PHP dan Python: Contoh dan perbandingan kod PHP dan Python: Contoh dan perbandingan kod Apr 15, 2025 am 12:07 AM

PHP dan Python mempunyai kelebihan dan kekurangan mereka sendiri, dan pilihannya bergantung kepada keperluan projek dan keutamaan peribadi. 1.PHP sesuai untuk pembangunan pesat dan penyelenggaraan aplikasi web berskala besar. 2. Python menguasai bidang sains data dan pembelajaran mesin.

PHP: Pengendalian pangkalan data dan logik sisi pelayan PHP: Pengendalian pangkalan data dan logik sisi pelayan Apr 15, 2025 am 12:15 AM

PHP menggunakan sambungan MySQLI dan PDO untuk berinteraksi dalam operasi pangkalan data dan pemprosesan logik sisi pelayan, dan memproses logik sisi pelayan melalui fungsi seperti pengurusan sesi. 1) Gunakan MySQLI atau PDO untuk menyambung ke pangkalan data dan laksanakan pertanyaan SQL. 2) Mengendalikan permintaan HTTP dan status pengguna melalui pengurusan sesi dan fungsi lain. 3) Gunakan urus niaga untuk memastikan atomik operasi pangkalan data. 4) Mencegah suntikan SQL, gunakan pengendalian pengecualian dan sambungan penutup untuk debugging. 5) Mengoptimumkan prestasi melalui pengindeksan dan cache, tulis kod yang sangat mudah dibaca dan lakukan pengendalian ralat.

Tujuan PHP: Membina Laman Web Dinamik Tujuan PHP: Membina Laman Web Dinamik Apr 15, 2025 am 12:18 AM

PHP digunakan untuk membina laman web dinamik, dan fungsi terasnya termasuk: 1. Menjana kandungan dinamik dan menghasilkan laman web secara real time dengan menyambung dengan pangkalan data; 2. Proses Interaksi Pengguna dan Penyerahan Bentuk, Sahkan Input dan Menanggapi Operasi; 3. Menguruskan sesi dan pengesahan pengguna untuk memberikan pengalaman yang diperibadikan; 4. Mengoptimumkan prestasi dan ikuti amalan terbaik untuk meningkatkan kecekapan dan keselamatan laman web.

Memilih antara php dan python: panduan Memilih antara php dan python: panduan Apr 18, 2025 am 12:24 AM

PHP sesuai untuk pembangunan web dan prototaip pesat, dan Python sesuai untuk sains data dan pembelajaran mesin. 1.Php digunakan untuk pembangunan web dinamik, dengan sintaks mudah dan sesuai untuk pembangunan pesat. 2. Python mempunyai sintaks ringkas, sesuai untuk pelbagai bidang, dan mempunyai ekosistem perpustakaan yang kuat.

See all articles