. Cara Berbeza untuk Menambah Kurungan

241. Cara Berbeza untuk Menambah Tanda Kurung

Kesukaran: Sederhana

Topik: Matematik, Rentetan, Pengaturcaraan Dinamik, Rekursi, Memoisasi

Memandangkan ungkapan rentetan nombor dan pengendali, kembalikan semua hasil yang mungkin daripada pengiraan semua kemungkinan cara yang berbeza untuk mengumpulkan nombor dan operator. Anda boleh mengembalikan jawapan dalam sebarang pesanan.

Kes ujian dijana supaya nilai output muat dalam integer 32-bit dan bilangan keputusan berbeza tidak melebihi 10⁴.

Contoh 1:

• Input: ungkapan = "2-1-1"
• Output: [0,2]
• Penjelasan:

  ((2-1)-1) = 0
  (2-(1-1)) = 2

Contoh 2:

• Input: ungkapan = "2*3-4*5"
• Output: [-34,-14,-10,-10,10]
• Penjelasan:

  (2*(3-(4*5))) = -34
  ((2*3)-(4*5)) = -14
  ((2*(3-4))*5) = -10
  (2*((3-4)*5)) = -10
  (((2*3)-4)*5) = 10

Kekangan:

• 1 <= ungkapan.panjang <= 20
• ungkapan terdiri daripada digit dan operator '+', '-' dan '*'.
• Semua nilai integer dalam ungkapan input berada dalam julat [0, 99].
• Nilai integer dalam ungkapan input tidak mempunyai '-' atau '+' di hadapan yang menandakan tanda.

Penyelesaian:

Kita boleh menggunakan rekursi digabungkan dengan memoisasi untuk menyimpan hasil yang dikira sebelum ini bagi sub-ungkapan, kerana ini mengelakkan pengiraan berlebihan dan mengoptimumkan penyelesaian.

Pendekatan:

1. Rekursi:

   • Untuk setiap operator dalam rentetan (+, -, *), kami membahagikan ungkapan pada operator itu.
   • Kira secara rekursif bahagian kiri dan kanan ungkapan.
   • Gabungkan hasil kedua-dua bahagian menggunakan operator.

2. Hafazan:

   • Simpan hasil subungkapan dalam tatasusunan bersekutu untuk mengelakkan pengiraan semula subungkapan yang sama beberapa kali.

3. Kes Asas:

   • Jika ungkapan mengandungi hanya nombor (iaitu, tiada pengendali), kembalikan nombor itu sebagai hasilnya.

Contoh Panduan:

Untuk input "2*3-4*5":

• Pisah pada * -> 2 dan 3-4*5
  • Hitung secara rekursif 3-4*5 dan 2, kemudian gabungkan.
• Berpisah pada - -> 2*3 dan 4*5
  • Hitung setiap satu secara rekursif dan gabungkan.
• Begitu juga untuk pecahan lain.

Mari laksanakan penyelesaian ini dalam PHP: 241. Cara Berbeza untuk Menambah Tanda Kurung

<?php
class Solution {

    /**
     * @var array
     */
    private $memo = [];

    /**
     * @param String $expression
     * @return Integer[]
     */
    public function diffWaysToCompute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $expression
     * @return array|mixed
     */
    private function compute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$expression1 = "2-1-1";
$expression2 = "2*3-4*5";
print_r($solution->diffWaysToCompute($expression1)); // Output: [0, 2]
print_r($solution->diffWaysToCompute($expression2)); // Output: [-34, -14, -10, -10, 10]
?>

Penjelasan:

1. Memoisasi: Tatasusunan $memo menyimpan hasil pengiraan untuk setiap ungkapan untuk mengelakkan pengiraan berlebihan.
2. Kes Asas: Apabila ungkapan adalah angka, ia ditukar kepada integer dan ditambahkan pada hasil.
3. Pemisahan Rekursif: Untuk setiap pengendali dalam ungkapan, bahagikannya kepada bahagian kiri dan kanan, hitung secara rekursif keputusan untuk kedua-dua bahagian, dan kemudian gabungkannya berdasarkan operator.
4. Contoh Penggunaan: Fungsi diffWaysToCompute diuji dengan contoh ungkapan untuk mengesahkan penyelesaian.

Pendekatan ini memastikan anda mengira semua hasil yang mungkin dengan cekap dengan memanfaatkan hafalan untuk mengelakkan pengiraan berlebihan.

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 . Cara Berbeza untuk Menambah Kurungan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!