Operasi Tolak Perdana

2601. Operasi Tolak Perdana

Kesukaran: Sederhana

Topik: Tatasusunan, Matematik, Carian Binari, Tamak, Teori Nombor

Anda diberi 0-diindeks nombor tatasusunan integer dengan panjang n.

Anda boleh melakukan operasi berikut seberapa banyak kali yang anda mahu:

• Pilih indeks i yang belum anda pilih sebelum ini, dan pilih p perdana kurang daripada angka[i], kemudian tolak p daripada nombor[i].

Kembali benar jika anda boleh menjadikan nombor tatasusunan yang semakin meningkat menggunakan operasi di atas dan palsu sebaliknya.

A tatasusunan yang semakin meningkat ialah tatasusunan yang setiap elemennya lebih besar daripada elemen sebelumnya.

Contoh 1:

• Input: nombor = [4,9,6,10]
• Output: benar
• Penjelasan: Dalam operasi pertama: Pilih i = 0 dan p = 3, dan kemudian tolak 3 daripada nombor[0], supaya nombor menjadi [1,9,6,10].
  • Dalam operasi kedua: i = 1, p = 7, tolak 7 daripada nombor[1], jadi nombor menjadi sama dengan [1,2,6,10].
  • Selepas operasi kedua, nombor diisih mengikut susunan yang semakin meningkat, jadi jawapannya adalah benar.

Contoh 2:

• Input: nombor = [6,8,11,12]
• Output: benar
• Penjelasan: Pada mulanya nombor diisih mengikut susunan yang semakin meningkat, jadi kami tidak perlu membuat sebarang operasi.

Contoh 3:

• Input: nombor = [5,8,3]
• Output: palsu
• Penjelasan: Dapat dibuktikan bahawa tiada cara untuk melakukan operasi untuk membuat nombor disusun mengikut susunan yang semakin meningkat, jadi jawapannya adalah palsu.

Kekangan:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• bilangan panjang == n

Petunjuk:

1. Fikirkan jika kita mempunyai banyak nombor perdana untuk ditolak daripada nombor[i]. Perdana mana yang lebih optimum?
2. Nombor perdana yang paling optimum untuk ditolak daripada nombor[i] ialah yang menjadikan nombor[i] terkecil mungkin dan lebih besar daripada nombor[i-1].

Penyelesaian:

Kita perlu memecahkan algoritma dan menyesuaikannya dengan sintaks dan fungsi PHP. Penyelesaian terutamanya melibatkan langkah-langkah berikut:

1. Menjana Perdana (Ayak Eratosthenes): Jana senarai semua nombor perdana sehingga nilai maksimum yang mungkin dalam nombor (1000).
2. Operasi Tolak Perdana: Untuk setiap nombor dalam nombor, semak sama ada kita boleh menolak nombor perdana untuk menjadikan tatasusunan meningkat dengan ketat.
3. Carian Perduaan untuk Perdana: Gunakan carian perduaan untuk mencari perdana terbesar kurang daripada nombor semasa yang masih akan mengekalkan jujukan meningkat dengan ketat.

Mari laksanakan penyelesaian ini dalam PHP: 2601. Operasi Tolak Perdana

primeSubOperation([4, 9, 6, 10]) ? 'true' : 'false';  // Output: true
echo $solution->primeSubOperation([6, 8, 11, 12]) ? 'true' : 'false'; // Output: true
echo $solution->primeSubOperation([5, 8, 3]) ? 'true' : 'false';      // Output: false
?>





  
  
  Penjelasan:




primeSubOperation: Gelung melalui setiap elemen dalam nombor dan semak jika kita boleh menjadikan setiap elemen lebih besar daripada yang sebelumnya dengan menolak perdana yang sesuai.


Kami menggunakan $this->findLargestPrimeLessThan untuk mencari prima terbesar kurang daripada num - prevNum.
Jika bilangan perdana sedemikian wujud, kami menolaknya daripada nombor semasa.
Jika selepas menolak perdana, nombor semasa tidak lebih besar daripada prevNum, kami mengembalikan palsu.
Jika tidak, kami mengemas kini prevNum kepada nombor semasa.


ayakEratosthenes: Menghasilkan semua nombor perdana sehingga 1000 menggunakan Ayakan Eratosthenes dan mengembalikannya sebagai tatasusunan.
findLargestPrimeLessThan: Menggunakan carian binari untuk mencari perdana terbesar kurang daripada had yang diberikan, memastikan kami menemui perdana optimum untuk penolakan.



  
  
  Analisis Kerumitan




Kerumitan Masa: O(n . √m), dengan n ialah panjang nombor dan m ialah nilai maksimum unsur dalam nombor (di sini m = 1000).

Kerumitan Angkasa: O(m), digunakan untuk menyimpan senarai nombor perdana sehingga 1000.


Penyelesaian ini akan mengembalikan benar atau salah berdasarkan sama ada mungkin untuk membuat angka meningkat dengan ketat dengan melakukan operasi tolak perdana yang diterangkan.

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