Tawarikh Pengekodan Typescript: Produk Tatasusunan Kecuali Diri

Pernyataan Masalah:

Memandangkan nombor tatasusunan integer, kembalikan jawapan tatasusunan supaya jawapan[i] adalah sama dengan hasil darab semua elemen nombor kecuali nombor[i].

Produk mana-mana awalan atau akhiran nombor dijamin muat dalam integer 32-bit.

Anda mesti menulis algoritma yang berjalan dalam masa O(n) dan tanpa menggunakan operasi bahagi.

Contoh 1:

• Input: nombor = [1,2,3,4]
• Output: [24,12,8,6]

Contoh 2:

• Input: nombor = [-1,1,0,-3,3]
• Output: [0,0,9,0,0]

Kekangan:

• 2 <= nums.length <= 10^5
• -30 <= angka[i] <= 30
• Produk mana-mana awalan atau akhiran nombor dijamin muat dalam integer 32-bit.

Susulan:

Bolehkah anda menyelesaikan masalah dalam O(1) kerumitan ruang tambahan? (Susun atur keluaran tidak dikira sebagai ruang tambahan untuk analisis kerumitan ruang.)

Proses Pemikiran Awal:

Untuk menyelesaikan masalah ini, kita perlu mengira hasil darab semua elemen kecuali elemen semasa tanpa menggunakan operasi bahagi. Ini boleh dilakukan dengan menggunakan dua hantaran ke atas tatasusunan:

1. Kira produk awalan untuk setiap elemen.
2. Hitung hasil akhiran untuk setiap elemen dan darab dengan hasil awalan.

Penyelesaian Asas:

Kita boleh menggunakan dua tatasusunan untuk menyimpan produk awalan dan akhiran, kemudian darabkannya untuk mendapatkan hasil akhir.

Kod:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Compute suffix products
    for (let i = n - 2; i >= 0; i--) {
        suffixProducts[i] = suffixProducts[i + 1] * nums[i + 1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan. Kami mengulangi tatasusunan sebanyak tiga kali.
• Kerumitan Angkasa: O(n), untuk menyimpan produk awalan dan akhiran.

Had:

Penyelesaian asas berfungsi dengan baik tetapi menggunakan ruang tambahan untuk menyimpan produk awalan dan akhiran.

Penyelesaian Dioptimumkan:

Kami boleh mengoptimumkan penyelesaian untuk menggunakan ruang tambahan O(1) dengan menggunakan tatasusunan output untuk menyimpan produk awalan dahulu dan kemudian mengubah suainya di tempat untuk memasukkan produk akhiran.

Kod:

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Compute suffix products and multiply with the prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}




<h3>
  
  
  Analisis Kerumitan Masa:
</h3>

<ul>
<li>
<strong>Kerumitan Masa:</strong> O(n), dengan n ialah panjang tatasusunan. Kami mengulangi tatasusunan dua kali.</li>
<li>
<strong>Kerumitan Angkasa:</strong> O(1), kerana kami menggunakan tatasusunan output untuk menyimpan hasil perantaraan dan tidak menggunakan sebarang ruang tambahan.</li>
</ul>

<h3>
  
  
  Penambahbaikan Daripada Penyelesaian Asas:
</h3>

<ul>
<li>Penyelesaian yang dioptimumkan mengurangkan kerumitan ruang kepada O(1) dengan menggunakan tatasusunan output untuk hasil perantaraan.</li>
</ul>

<h2>
  
  
  Kes Edge dan Ujian:
</h2>

<h3>
  
  
  Kes Tepi:
</h3>

<ol>
<li> Tatasusunan mengandungi sifar.</li>
<li> Tatasusunan mengandungi nombor negatif.</li>
<li>Panjang tatasusunan ialah had minimum (2) atau maksimum (10^5).</li>
</ol>

<h3>
  
  
  Kes Ujian:
</h3>



<pre class="brush:php;toolbar:false">console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

Strategi Penyelesaian Masalah Umum:

1. Fahami Masalah: Baca pernyataan masalah dengan teliti untuk memahami keperluan dan kekangan.
2. Kenal pasti Operasi Utama: Tentukan operasi utama yang diperlukan, seperti pengiraan produk awalan dan akhiran.
3. Optimumkan untuk Kebolehbacaan: Gunakan logik yang jelas dan padat untuk memastikan kod mudah diikuti.
4. Uji Dengan Teliti: Uji penyelesaian dengan pelbagai kes, termasuk kes tepi, untuk memastikan ketepatan.

Mengenalpasti Masalah Serupa:

1. Susun Susun Awalan:

   • Masalah di mana anda perlu mengira jumlah awalan untuk pertanyaan julat.
   • Contoh: Pertanyaan Jumlah Julat.

2. Algoritma Di Tempat:

   • Masalah di mana operasi perlu dilakukan di tempat dengan ruang tambahan yang terhad.
   • Contoh: Putar tatasusunan ke kanan dengan k langkah.

3. Manipulasi Tatasusunan:

   • Masalah di mana anda perlu mengubah suai tatasusunan berdasarkan keadaan tertentu.
   • Contoh: Alihkan sifar ke penghujung tatasusunan.

Kesimpulan:

• Masalah pengiraan hasil tatasusunan kecuali diri boleh diselesaikan dengan cekap menggunakan kedua-dua pendekatan asas dengan ruang tambahan dan pendekatan di tempat yang dioptimumkan.
• Memahami masalah dan membahagikannya kepada bahagian yang boleh diurus adalah penting.
• Menggunakan logik yang jelas dan mengoptimumkan kebolehbacaan memastikan penyelesaiannya mudah diikuti.
• Pengujian dengan pelbagai kes tepi memastikan keteguhan.
• Mengenal corak dalam masalah boleh membantu menggunakan penyelesaian yang serupa untuk cabaran lain.

Dengan mempraktikkan masalah dan strategi sedemikian, anda boleh meningkatkan kemahiran menyelesaikan masalah anda dan lebih bersedia untuk pelbagai cabaran pengekodan.

Atas ialah kandungan terperinci Tawarikh Pengekodan Typescript: Produk Tatasusunan Kecuali Diri. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!