Rumah > Artikel > pembangunan bahagian belakang > Cari Panjang Awalan Biasa Terpanjang
3043. Cari Panjang Awalan Biasa Terpanjang
Kesukaran: Sederhana
Topik: Tatasusunan, Jadual Hash, Rentetan, Percubaan
Anda diberi dua tatasusunan dengan positif integer arr1 dan arr2.
A awalan integer positif ialah integer yang dibentuk oleh satu atau lebih digitnya, bermula daripada digit paling kirinya. Contohnya, 123 ialah awalan bagi integer 12345, manakala 234 ialah bukan.
A awalan biasa daripada dua integer a dan b ialah integer c, sehingga c ialah awalan bagi kedua-dua a dan b. Contohnya, 5655359 dan 56554 mempunyai awalan biasa 565 manakala 1223 dan 43456 tidak mempunyai awalan biasa.
Anda perlu mencari panjang awalan sepunya terpanjang antara semua pasangan integer (x, y) supaya x tergolong dalam arr1 dan y tergolong dalam arr2.
Kembalikan panjang terpanjang awalan biasa antara semua pasangan. Jika tiada awalan biasa wujud di kalangan mereka, kembalikan 0.
Contoh 1:
Contoh 2:
Kekangan:
Petunjuk:
Penyelesaian:
Kami boleh menggunakan HashSet untuk menyimpan awalan daripada satu tatasusunan dan kemudian semak awalan tersebut dalam tatasusunan kedua.
Jana Awalan: Untuk setiap nombor dalam arr1 dan arr2, jana semua awalan yang mungkin. Awalan dibentuk oleh satu atau lebih digit bermula dari digit paling kiri.
Simpan Awalan arr1 dalam Set: Menggunakan HashSet untuk menyimpan semua awalan nombor dalam arr1 memastikan carian pantas apabila menyemak awalan daripada arr2.
Cari Awalan Biasa Terpanjang: Untuk setiap nombor dalam arr2, hasilkan awalannya dan semak sama ada mana-mana awalan ini wujud dalam HashSet dari langkah 2. Jejaki awalan terpanjang ditemui.
Kembalikan Panjang Awalan Biasa Terpanjang: Jika awalan biasa ditemui, kembalikan panjangnya; jika tidak, kembalikan 0.
Mari laksanakan penyelesaian ini dalam PHP: 3043. Cari Panjang Awalan Biasa Terpanjang
Penjelasan:
Penciptaan HashSet:
- Kami mula-mula mencipta tatasusunan bersekutu $prefixSet untuk menahan semua kemungkinan awalan nombor dalam arr1.
- Kami mengulangi setiap nombor dalam arr1, menukarnya kepada rentetan dan mengekstrak semua awalannya menggunakan fungsi substr. Setiap awalan disimpan dalam $prefixSet.
Semakan Awalan:
- Seterusnya, kami mengulangi setiap nombor dalam arr2, menukarnya kepada rentetan juga.
- Untuk setiap nombor dalam arr2, kami sekali lagi mengeluarkan semua kemungkinan awalan.
- Jika awalan wujud dalam $prefixSet, kami menyemak sama ada panjangnya lebih besar daripada panjang maksimum semasa yang ditemui ($maxLength).
Kembalikan Keputusan:
- Akhir sekali, kami mengembalikan panjang awalan biasa terpanjang yang ditemui.
Kerumitan:
Penyelesaian ini cekap dan berfungsi dengan baik dalam kekangan yang disediakan.
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:
Atas ialah kandungan terperinci Cari Panjang Awalan Biasa Terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!