Bilangan Maksimum Integer untuk Dipilih Daripada Julat I

2554. Bilangan Integer Maksimum untuk Dipilih Daripada Julat I

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Carian Binari, Tamak, Isih

Anda diberi tatasusunan integer dilarang dan dua integer n dan maxSum. Anda memilih beberapa bilangan integer mengikut peraturan di bawah:

• Integer yang dipilih mestilah dalam julat [1, n].
• Setiap integer boleh dipilih paling banyak sekali.
• Integer yang dipilih tidak seharusnya berada dalam tatasusunan yang dilarang.
• Jumlah integer yang dipilih tidak boleh melebihi maxSum.

Kembalikan bilangan maksimum integer yang anda boleh pilih mengikut peraturan yang dinyatakan.

Contoh 1:

• Input: dilarang = [1,6,5], n = 5, maxSum = 6
• Output: 2
• Penjelasan: Anda boleh memilih integer 2 dan 4.
  • 2 dan 4 adalah daripada julat [1, 5], kedua-duanya tidak muncul dalam larangan, dan jumlahnya ialah 6, yang tidak melebihi maxSum.

Contoh 2:

• Input: dilarang = [1,2,3,4,5,6,7], n = 8, maxSum = 1
• Output: 0
• Penjelasan: Anda tidak boleh memilih sebarang integer semasa mengikut syarat yang dinyatakan.

Contoh 3:

• Input: diharamkan = [11], n = 7, maxSum = 50
• Output: 7
• Penjelasan: Anda boleh memilih integer 1, 2, 3, 4, 5, 6, dan 7.
  • Mereka daripada julat [1, 7], semuanya tidak muncul dalam larangan, dan jumlah mereka ialah 28, yang tidak melebihi maxSum.

Kekangan:

• 1 4
• 1 4
• 1 9

Petunjuk:

1. Simpan nombor larangan yang kurang daripada n dalam satu set.
2. Gelung pada nombor dari 1 hingga n dan jika nombor itu tidak diharamkan, gunakannya.
3. Teruskan menambah nombor semasa ia tidak diharamkan dan jumlahnya kurang daripada k.

Penyelesaian:

Kita boleh menggunakan pendekatan tamak di mana kita mengulangi nombor dari 1 hingga n, melangkau nombor yang dilarang dan terus menambah nombor yang sah (yang tiada dalam tatasusunan larangan) kepada jumlah berjalan sehingga kita mencapai maxSum.

Berikut ialah penyelesaian langkah demi langkah:

Langkah-langkah:

1. Tukar tatasusunan yang dilarang kepada set untuk carian pantas: Menggunakan array_flip() boleh menukar tatasusunan yang dilarang menjadi set untuk carian kerumitan masa purata O(1).
2. Lelar dari 1 hingga n: Semak setiap nombor, jika ia tiada dalam set larangan dan jika menambahnya tidak melebihi maxSum, tambahkannya pada jumlah dan tambahkan kiraan.
3. Berhenti sekali menambah nombor seterusnya melebihi maxSum: Memandangkan matlamatnya adalah untuk memaksimumkan bilangan integer yang dipilih tanpa melebihi jumlah, pendekatan tamak ini memastikan kami mengambil nombor terkecil yang ada dahulu.

Pendekatan:

1. Kecualikan Nombor Diharamkan: Kami akan menjejaki nombor yang dilarang dalam satu set (atau tatasusunan bersekutu) untuk carian pantas.
2. Pemilihan Tamak: Mula memilih nombor dari 1 hingga n dalam tertib menaik, kerana ini akan membolehkan kami memaksimumkan bilangan integer yang dipilih. Setiap kali kami memilih nombor, kami akan menambahkannya pada jumlah dan menyemak sama ada ia melebihi maxSum. Jika ya, berhenti.
3. Pertimbangan Kecekapan: Memandangkan kita mengulangi nombor dari 1 kepada n, dan menyemak sama ada setiap satu dalam set yang dilarang (yang boleh dilakukan dalam masa tetap), pendekatan berjalan dalam masa linear berbanding dengan n dan saiz senarai larangan.

Mari kita laksanakan penyelesaian ini dalam PHP: 2554. Bilangan Integer Maksimum untuk Dipilih Daripada Julat I

<?php /**
 * @param Integer[] $banned
 * @param Integer $n
 * @param Integer $maxSum
 * @return Integer
 */
function maxCount($banned, $n, $maxSum) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxCount([1, 6, 5], 5, 6);  // Output: 2
echo "\n";
echo maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1);  // Output: 0
echo "\n";
echo maxCount([11], 7, 50);  // Output: 7
?>

Penjelasan:

1. Tukar tatasusunan terlarang untuk ditetapkan:
   
   Kami menggunakan array_flip($banned) untuk mencipta set daripada tatasusunan yang dilarang, yang membolehkan carian O(1) untuk menyemak sama ada nombor dilarang.

2. Lelaran daripada 1 hingga n:
   
   Kami berulang melalui nombor dari 1 hingga n. Untuk setiap nombor:

   • Jika nombor itu tiada dalam set larangan (ditanda menggunakan isset($bannedSet[$i])),
   • Dan jika menambah nombor pada jumlah tidak melebihi maxSum,
   • Kami memasukkan nombor itu dan mengemas kini jumlah serta kiraan.

3. Kembalikan kiraan:
   
   Selepas gelung, kami mengembalikan bilangan integer yang dipilih ($kiraan).

4. $bannedSet = array_flip($banned);: Ini menukar senarai larangan kepada satu set (susunan bersekutu) untuk carian pantas.

5. untuk ($i = 1; $i : Kami mengulangi semua integer dari 1 hingga n.

6. if (isset($bannedSet[$i])) { teruskan; }: Ini menyemak sama ada nombor semasa berada dalam set yang dilarang. Jika ya, kami melangkaunya.

7. jika ($sum $i > $maxSum) { break; }: Jika menambah nombor semasa melebihi maxSum, kami menghentikan proses.

8. $sum = $i; $count ;: Jika nombor itu sah dan menambahnya tidak melebihi maxSum, kami memasukkannya ke dalam jumlah kami dan meningkatkan kiraan.

Kerumitan Masa:

• Penciptaan set terlarang (array_flip) ialah O(b), dengan b ialah panjang array terlarang.
• Gelung berulang n kali (untuk nombor dari 1 hingga n), dan setiap carian ke dalam set yang dilarang mengambil masa O(1). Jadi, kerumitan masa gelung ialah O(n).
• Oleh itu, kerumitan masa keseluruhan ialah O(n b), yang cekap memandangkan kekangan masalah.

Contoh Panduan:

Untuk input:

• Input 1: dilarang = [1, 6, 5], n = 5, maxSum = 6

  • Kami mencipta set terlarang: {1, 5, 6}.
  • Kami berulang melalui nombor 1 hingga 5:
    • 1 dilarang, langkau.
    • 2 tidak diharamkan, tambahkannya kepada jumlah (jumlah = 2, kiraan = 1).
    • 3 tidak diharamkan, tambahkannya kepada jumlah (jumlah = 5, kiraan = 2).
    • 4 tidak dilarang, tetapi menambahkannya pada jumlah akan melebihi maxSum (5 4 = 9), jadi langkau.
  • Hasilnya ialah 2.

• Input 2: dilarang = [1, 2, 3, 4, 5, 6, 7], n = 8, maxSum = 1

  • Semua nombor dari 1 hingga 7 dilarang, jadi tiada nombor yang sah boleh dipilih.
  • Hasilnya ialah 0.

• Input 3: diharamkan = [11], n = 7, maxSum = 50

  • Satu-satunya nombor yang dilarang ialah 11, iaitu di luar julat 1 hingga 7.
  • Kita boleh memilih semua nombor dari 1 hingga 7, dan jumlahnya ialah 28, iaitu kurang daripada maxSum.
  • Hasilnya ialah 7.

Penyelesaian ini cekap mengendalikan masalah dalam kekangan yang diberikan.

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 Bilangan Maksimum Integer untuk Dipilih Daripada Julat I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!