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

王林
Lepaskan: 2024-09-06 18:30:35
asal
1075 orang telah melayarinya

Mastering Array Manipulation in DSA using JavaScript: From Basics to Advanced

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
Salin selepas log masuk

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]);
}
Salin selepas log masuk

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));
Salin selepas log masuk

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);
}
Salin selepas log masuk

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]
Salin selepas log masuk

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]
Salin selepas log masuk

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]
Salin selepas log masuk

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]
Salin selepas log masuk

Kerumitan Masa: O(1)

4.2 Pemadaman dari awal

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

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]
Salin selepas log masuk

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
Salin selepas log masuk

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
Salin selepas log masuk

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]
Salin selepas log masuk

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
Salin selepas log masuk

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
Salin selepas log masuk

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]
Salin selepas log masuk

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!

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan