Lembaran Segiempat Terpanjang dalam Tatasusunan

2501. Garisan Segiempat Terpanjang dalam Susunan

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Carian Binari, Pengaturcaraan Dinamik, Isih

Anda diberi nombor tatasusunan integer. Susunan nombor dipanggil coretan segi empat sama jika:

• Panjang urutan sekurang-kurangnya 2, dan
• selepas mengisih urutan, setiap elemen (kecuali elemen pertama) ialah petak nombor sebelumnya.

Kembali panjang jalur segi empat sama terpanjang dalam angka, atau kembalikan -1 jika tiada jalur segi empat sama.

Satu susulan ialah tatasusunan yang boleh diterbitkan daripada tatasusunan lain dengan memadamkan beberapa atau tiada unsur tanpa mengubah susunan unsur yang tinggal.

Contoh 1:

• Input: nombor = [4,3,6,16,8,2]
• Output: 3
• Penjelasan: Pilih urutan [4,16,2]. Selepas menyusunnya, ia menjadi [2,4,16].
  • 4 = 2 * 2.
  • 16 = 4 * 4.
  • Oleh itu, [4,16,2] ialah coretan segi empat sama.
  • Ia boleh ditunjukkan bahawa setiap urutan panjang 4 bukanlah coretan segi empat sama.

Contoh 2:

• Input: nombor = [2,3,5,6,7]
• Output: -1
• Penjelasan: Tiada coretan segi empat sama dalam angka jadi kembalikan -1.

Kekangan:

• 2 <= nums.length <= 10⁵
• 2 <= angka[i] <= 10⁵

Petunjuk:

1. Dengan kekangan, panjang coretan segi empat sama terpanjang mungkin ialah 5.
2. Simpan elemen nombor dalam satu set untuk menyemak dengan cepat sama ada ia wujud.

Penyelesaian:

Kita perlu mengenal pasti coretan segi empat sama terpanjang dalam tatasusunan nums. Garisan segi empat sama ialah jujukan dengan setiap unsur berikutnya ialah segi empat sama unsur sebelumnya dan panjangnya mestilah sekurang-kurangnya dua unsur.

Berikut ialah pendekatan penyelesaian:

1. Gunakan Set untuk Carian Pantas:

   • Simpan nombor dalam satu set untuk mengesahkan dengan cepat sama ada segi empat sama elemen turut berada dalam tatasusunan.

2. Lelar Melalui Tatasusunan:

   • Untuk setiap nombor dalam tatasusunan, cuba bina coretan segi empat sama bermula daripada nombor itu.
   • Periksa sama ada kuasa dua nombor semasa wujud dalam set dan teruskan rentetan sehingga tiada padanan kuasa dua lagi.

3. Jejak Panjang Maksimum:

   • Jejaki panjang maksimum semua jalur segi empat sama yang mungkin ditemui. Jika tiada coretan segi empat sama ditemui, kembalikan -1.

4. Pengoptimuman:

   • Isih tatasusunan sebelum menyemak setiap elemen untuk memastikan urutan disemak dalam tertib menaik. Ini akan membantu mengelakkan pemeriksaan berlebihan.

Mari laksanakan penyelesaian ini dalam PHP: 2501. Garisan Segiempat Terpanjang dalam Tatasusunan

  
  
  Penjelasan:




Isih: Isih nombor memastikan kami boleh menyemak urutan dalam tertib menaik.

Tetapkan Carian: Menggunakan array_flip mencipta struktur seperti set untuk $numSet dengan $nums sebagai kunci, membolehkan semakan kewujudan pantas.

Gelung setiap nombor: Untuk setiap nombor dalam nombor, semak sama ada kuasa dua nombor semasa berada dalam set. Jika ya, teruskan coretan. Jika tidak, putuskan coretan itu dan semak sama ada ia adalah yang paling lama ditemui.



  
  
  Analisis Kerumitan




Kerumitan Masa: O(n log n) disebabkan oleh pengisihan, dengan n ialah bilangan elemen dalam nombor. Carian seterusnya dan semakan coretan segi empat sama ialah O(n).

Kerumitan Ruang: O(n), terutamanya untuk menyimpan nombor dalam set.


Penyelesaian ini mencari coretan persegi terpanjang dengan cekap atau mengembalikan -1 jika tiada coretan yang sah wujud.

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 Lembaran Segiempat Terpanjang dalam Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!