Tawarikh Pengekodan TypeScript: Meningkatkan Susunan Tiga Kali

Pernyataan Masalah:

Memandangkan nombor tatasusunan integer, kembalikan benar jika wujud tiga ganda indeks (i, j, k) supaya i < j < k dan nombor[i] < nombor[j] < bilangan [k]. Jika tiada indeks sedemikian wujud, kembalikan palsu.

Contoh 1:

• Input: nombor = [1,2,3,4,5]
• Output: benar
• Penjelasan: Mana-mana triplet di mana saya < j < k adalah sah.

Contoh 2:

• Input: nombor = [5,4,3,2,1]
• Output: palsu
• Penjelasan: Tiada triplet wujud.

Contoh 3:

• Input: nombor = [2,1,5,0,4,6]
• Output: benar
• Penjelasan: Triplet (3, 4, 5) adalah sah kerana num[3] == 0 < nombor[4] == 4 < nombor[5] == 6.

Kekangan:

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= angka[i] <= 2^31 - 1

Susulan:

Bolehkah anda melaksanakan penyelesaian yang berjalan dalam kerumitan masa O(n) dan kerumitan ruang O(1)?

Proses Pemikiran Awal:

Untuk menyelesaikan masalah ini dengan cekap, kita perlu menjejaki nilai terkecil dan kedua terkecil yang ditemui setakat ini. Jika kita menemui nilai ketiga yang lebih besar daripada nilai kedua terkecil, maka kita telah menemui tiga kali ganda yang semakin meningkat.

Penyelesaian Asas (Brute Force):

Penyelesaian brute force melibatkan pemeriksaan semua kembar tiga yang mungkin untuk melihat sama ada wujud satu yang memenuhi syarat i < j < k dan nombor[i] < nombor[j] < bilangan [k]. Pendekatan ini mempunyai kerumitan masa O(n^3), yang tidak cekap untuk saiz input yang besar.

Kod:

function increasingTripletBruteForce(nums: number[]): boolean {
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }
    return false;
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n^3), dengan n ialah panjang tatasusunan. Ini kerana kami sedang menyemak semua kemungkinan kembar tiga.
• Kerumitan Angkasa: O(1), kerana kami tidak menggunakan sebarang ruang tambahan.

Had:

Penyelesaian brute force tidak cekap dan tidak sesuai untuk saiz input yang besar.

Penyelesaian Dioptimumkan:

Penyelesaian yang dioptimumkan melibatkan lelaran melalui tatasusunan sambil mengekalkan dua pembolehubah, pertama dan kedua, yang mewakili nilai terkecil dan kedua terkecil yang ditemui setakat ini. Jika kita mendapati nilai yang lebih besar daripada saat, maka kita akan kembali benar.

Kod:

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (let num of nums) {
        if (num <= first) {
            first = num; // smallest value
        } else if (num <= second) {
            second = num; // second smallest value
        } else {
            return true; // found a value greater than second smallest, thus an increasing triplet exists
        }
    }

    return false;
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan. Kami mengulangi tatasusunan sekali.
• Kerumitan Angkasa: O(1), kerana kami hanya menggunakan jumlah ruang tambahan yang tetap.

Penambahbaikan Daripada Penyelesaian Asas:

• Penyelesaian ini berjalan dalam masa linear dan menggunakan ruang malar, menjadikannya optimum untuk kekangan yang diberikan.

Kes Edge dan Ujian:

Kes Tepi:

1. Tatasusunan berada dalam susunan menurun.
2. Tatasusunan mengandungi tepat tiga elemen dalam susunan yang semakin meningkat.
3. Tatasusunan mempunyai bilangan elemen yang banyak tanpa tiga kali ganda yang meningkat.
4. Tatasusunan mengandungi pendua.

Kes Ujian:

console.log(increasingTripletBruteForce([1,2,3,4,5])); // true
console.log(increasingTripletBruteForce([5,4,3,2,1])); // false
console.log(increasingTripletBruteForce([2,1,5,0,4,6])); // true
console.log(increasingTripletBruteForce([1,1,1,1,1])); // false
console.log(increasingTripletBruteForce([1,2])); // false
console.log(increasingTripletBruteForce([1,2,3])); // true
console.log(increasingTripletBruteForce([1,5,0,4,1,3])); // true

console.log(increasingTriplet([1,2,3,4,5])); // true
console.log(increasingTriplet([5,4,3,2,1])); // false
console.log(increasingTriplet([2,1,5,0,4,6])); // true
console.log(increasingTriplet([1,1,1,1,1])); // false
console.log(increasingTriplet([1,2])); // false
console.log(increasingTriplet([1,2,3])); // true
console.log(increasingTriplet([1,5,0,4,1,3])); // true

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 menjejak nilai terkecil dan kedua terkecil.
3. Optimumkan untuk Kecekapan: Gunakan algoritma dan struktur data yang cekap untuk meminimumkan kerumitan masa dan ruang.
4. Uji Dengan Teliti: Uji penyelesaian dengan pelbagai kes, termasuk kes tepi, untuk memastikan ketepatan.

Mengenalpasti Masalah Serupa:

1. Masalah Subray:

   • Masalah di mana anda perlu mencari subarray dengan sifat tertentu.
   • Contoh: Mencari subarray jumlah maksimum (Algoritma Kadane).

2. Teknik Dua Mata:

   • Masalah menggunakan dua penunjuk boleh membantu mengoptimumkan penyelesaian.
   • Contoh: Mengalih keluar pendua daripada tatasusunan yang diisih.

3. Algoritma Di Tempat:

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

Kesimpulan:

• Masalah mencari jujukan triplet yang semakin meningkat boleh diselesaikan dengan cekap menggunakan kedua-dua pendekatan kekerasan dan penyelesaian yang dioptimumkan dengan masa linear dan kerumitan ruang yang berterusan.
• Memahami masalah dan membahagikannya kepada bahagian yang boleh diurus adalah penting.
• Menggunakan algoritma yang cekap memastikan penyelesaian adalah optimum untuk input yang besar.
• 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: Meningkatkan Susunan Tiga Kali. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!