Menguasai Manipulasi Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan

Menguasai Manipulasi Tatasusunan dalam JavaScript untuk DSA

Tatasusunan ialah struktur data asas dalam sains komputer dan digunakan secara meluas dalam pelbagai algoritma dan senario penyelesaian masalah. Panduan komprehensif ini akan membawa anda melalui perkara-perkara penting dalam manipulasi tatasusunan dalam JavaScript, meliputi topik dari peringkat asas hingga lanjutan. Kami akan meneroka traversal, sisipan, pemadaman, carian dan banyak lagi, bersama-sama dengan kerumitan masa dan contoh praktikalnya.

Jadual Kandungan

1. Pengenalan kepada Tatasusunan
2. Traversal Tatasusunan
3. Sisipan dalam Tatasusunan
4. Pemadaman dalam Tatasusunan
5. Mencari dalam Tatasusunan
6. Teknik Manipulasi Tatasusunan Lanjutan
7. Masalah Amalan
8. Pautan Masalah LeetCode

1. Pengenalan kepada Tatasusunan

Susun atur ialah koleksi elemen yang disimpan di lokasi memori bersebelahan. Dalam JavaScript, tatasusunan adalah dinamik dan boleh menyimpan elemen jenis yang berbeza.

Operasi tatasusunan asas:

// Creating an array
let arr = [1, 2, 3, 4, 5];

// Accessing elements
console.log(arr[0]); // Output: 1

// Modifying elements
arr[2] = 10;
console.log(arr); // Output: [1, 2, 10, 4, 5]

// Getting array length
console.log(arr.length); // Output: 5

Kerumitan Masa:

• Mengakses elemen: O(1)
• Mengubah suai elemen: O(1)
• Mendapatkan panjang tatasusunan: O(1)

2. Array Traversal

Traversal bermaksud melawati setiap elemen tatasusunan sekali. Terdapat beberapa cara untuk melintasi tatasusunan dalam JavaScript.

2.1 Menggunakan gelung for

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

Kerumitan Masa: O(n), dengan n ialah bilangan elemen dalam tatasusunan.

2.2 Menggunakan forEach

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

Kerumitan Masa: O(n)

2.3 Menggunakan untuk...daripada gelung

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

Kerumitan Masa: O(n)

3. Sisipan dalam Tatasusunan

Pemasukan dalam tatasusunan boleh dilakukan pada permulaan, akhir atau pada kedudukan tertentu.

3.1 Sisipan pada akhir

let arr = [1, 2, 3];
arr.push(4);
console.log(arr); // Output: [1, 2, 3, 4]

Kerumitan Masa: O(1) (dilunaskan)

3.2 Sisipan pada permulaan

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

Kerumitan Masa: O(n), kerana semua elemen sedia ada perlu dianjak

3.3 Sisipan pada kedudukan tertentu

let arr = [1, 2, 4, 5];
arr.splice(2, 0, 3);
console.log(arr); // Output: [1, 2, 3, 4, 5]

Kerumitan Masa: O(n), kerana elemen selepas titik sisipan perlu dianjak

4. Pemadaman dalam Tatasusunan

Serupa dengan sisipan, pemadaman boleh dilakukan pada permulaan, akhir atau pada kedudukan tertentu.

4.1 Pemadaman dari penghujung

let arr = [1, 2, 3, 4];
arr.pop();
console.log(arr); // Output: [1, 2, 3]

Kerumitan Masa: O(1)

4.2 Pemadaman dari awal

let arr = [1, 2, 3, 4];
arr.shift();
console.log(arr); // Output: [2, 3, 4]

Kerumitan Masa: O(n), kerana semua elemen yang tinggal perlu dianjak

4.3 Pemadaman pada kedudukan tertentu

let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
console.log(arr); // Output: [1, 2, 4, 5]

Kerumitan Masa: O(n), kerana elemen selepas titik pemadaman perlu dialihkan

5. Mencari dalam Tatasusunan

Mencari ialah operasi biasa yang dilakukan pada tatasusunan. Mari lihat beberapa teknik carian.

5.1 Carian Linear

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1

Kerumitan Masa: O(n)

5.2 Carian Binari (untuk tatasusunan yang disusun)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1

Kerumitan Masa: O(log n)

6. Teknik Manipulasi Susunan Lanjutan

Sekarang mari kita terokai beberapa teknik yang lebih maju untuk manipulasi tatasusunan.

6.1 Teknik Dua Penunjuk

Teknik dua mata sering digunakan untuk menyelesaikan masalah tatasusunan dengan cekap. Berikut ialah contoh menggunakan dua penunjuk untuk membalikkan tatasusunan di tempat:

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

let arr = [1, 2, 3, 4, 5];
reverseArray(arr);
console.log(arr); // Output: [5, 4, 3, 2, 1]

Kerumitan Masa: O(n)

6.2 Teknik Tingkap Gelongsor

Teknik tingkap gelongsor berguna untuk menyelesaikan masalah subarray. Berikut ialah contoh untuk mencari jumlah subarray maksimum saiz k:

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39

Kerumitan Masa: O(n)

6.3 Algoritma Kadane

Algoritma Kadane digunakan untuk mencari jumlah subarray maksimum dalam tatasusunan. Ini adalah contoh pengaturcaraan dinamik:

function kadane(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7

Kerumitan Masa: O(n)

6.4 Algoritma Bendera Kebangsaan Belanda

Algoritma ini digunakan untuk mengisih tatasusunan yang mengandungi hanya 0s, 1s dan 2s:

function dutchNationalFlag(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
}

let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]

Kerumitan Masa: O(n)

7. Masalah Amalan

Berikut adalah 50 masalah amalan dari peringkat mudah hingga lanjutan. Sebahagian daripada ini adalah daripada LeetCode, manakala yang lain ialah senario manipulasi tatasusunan biasa:

1. Jumlah semua elemen dalam tatasusunan
2. Cari elemen maksimum dalam tatasusunan
3. Terbalikkan tatasusunan di tempat
4. Alih keluar pendua daripada tatasusunan yang diisih
5. Putar tatasusunan dengan k langkah
6. Cari elemen kedua terbesar dalam tatasusunan
7. Gabungkan dua tatasusunan yang diisih
8. Cari nombor yang hilang dalam tatasusunan 1 hingga n
9. Alihkan semua sifar ke penghujung tatasusunan
10. Cari persilangan dua tatasusunan
11. Cari gabungan dua tatasusunan
12. Semak sama ada tatasusunan ialah subset tatasusunan lain
13. Cari indeks keseimbangan dalam tatasusunan
14. Susun semula nombor positif dan negatif dalam tatasusunan
15. Cari elemen majoriti dalam tatasusunan
16. Cari elemen puncak dalam tatasusunan
17. Laksanakan tatasusunan bulat
18. Cari nombor positif terkecil yang hilang dalam tatasusunan
19. Masalah Air Hujan Memerangkap
20. Laksanakan tindanan menggunakan tatasusunan
21. Laksanakan baris gilir menggunakan tatasusunan
22. Cari urutan yang paling lama meningkat
23. Laksanakan carian binari dalam tatasusunan diisih yang diputar
24. Cari jumlah maksimum subarray saiz k
25. Laksanakan algoritma Kadane
26. Cari bilangan minimum platform yang diperlukan untuk stesen kereta api
27. Cari subarray terpanjang dengan nombor yang sama 0s dan 1s
28. Melaksanakan algoritma Bendera Kebangsaan Belanda
29. Cari subarray terkecil dengan jumlah lebih besar daripada nilai yang diberikan
30. Laksanakan algoritma Pengundian Majoriti Boyer-Moore
31. Cari subarray produk maksimum
32. Laksanakan algoritma Permainan Lompat
33. Cari elemen yang lebih besar seterusnya untuk setiap elemen dalam tatasusunan
34. Laksanakan algoritma Maksimum Tetingkap Gelongsor
35. Cari subrentetan terpanjang tanpa mengulang aksara
36. Laksanakan algoritma Selang Gabungan
37. Cari bilangan lompatan minimum untuk mencapai penghujung tatasusunan
38. Melaksanakan algoritma Jual Beli Saham untuk Memaksimumkan Untung
39. Cari Substring Palindromik Terpanjang
40. Laksanakan algoritma Susunan Biasa Terpanjang
41. Cari Subarray Berterusan Tidak Diisih Terpendek
42. Melaksanakan Algoritma Bekas Dengan Kebanyakan Air
43. Cari Urutan Berturut-turut Terpanjang dalam tatasusunan
44. Melaksanakan algoritma Produk Maksimum Tiga Nombor
45. Cari Elemen Terbesar Kth dalam Tatasusunan
46. Laksanakan Cari Semua Pendua dalam algoritma Tatasusunan
47. Cari Jumlah Subarray Saiz Minimum
48. Melaksanakan Produk Array Kecuali algoritma Kendiri
49. Cari Jurang Maksimum dalam tatasusunan yang diisih
50. Melaksanakan Algoritma Median Dua Tatasusunan Diisih

8. Pautan Masalah LeetCode

Berikut ialah 20 masalah LeetCode untuk menguji kemahiran manipulasi tatasusunan anda:

1. Dua Jumlah
2. Masa Terbaik untuk Membeli dan Menjual Stok
3. Mengandungi Pendua
4. Produk Susunan Kecuali Diri
5. Subarray Maksimum
6. Gabung Selang
7. 3Jumlah
8. Bekas dengan Kebanyakan Air
9. Susun Putar
10. Cari dalam Tatasusunan Isih Diputar
11. Cari Minimum dalam Tatasusunan Isih Diputar
12. Permutasi Seterusnya
13. Jumlah Subarray Sama dengan K
14. Matriks Lingkaran
15. Permainan Lompat
16. Jujukan Berturut-turut Terpanjang
17. Cari Semua Pendua dalam Tatasusunan
18. Kth Elemen Terbesar dalam Tatasusunan
19. Memerangkap Air Hujan
20. Median Dua Tatasusunan Isih

Dengan menyelesaikan masalah ini dan memahami konsep asas, anda akan meningkatkan kemahiran manipulasi tatasusunan anda dengan ketara dalam JavaScript untuk Struktur Data dan Algoritma.

Ingat, kunci untuk menguasai teknik ini ialah amalan yang konsisten dan memahami kerumitan masa dan ruang bagi penyelesaian anda.

Selamat mengekod!

Atas ialah kandungan terperinci Menguasai Manipulasi Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!