Traversal Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Teknik Lanjutan

Traversal tatasusunan ialah konsep asas dalam Struktur Data dan Algoritma (DSA) yang harus dikuasai oleh setiap pembangun. Dalam panduan komprehensif ini, kami akan meneroka pelbagai teknik untuk merentasi tatasusunan dalam JavaScript, bermula daripada pendekatan asas dan maju kepada kaedah yang lebih maju. Kami akan merangkumi 20 contoh, daripada peringkat mudah hingga lanjutan dan memasukkan soalan gaya LeetCode untuk mengukuhkan pembelajaran anda.

Jadual Kandungan

1. Pengenalan kepada Array Traversal
2. Traversal Tatasusunan Asas
   • Contoh 1: Menggunakan gelung for
   • Contoh 2: Menggunakan gelung sementara
   • Contoh 3: Menggunakan gelung do-while
   • Contoh 4: Rentas songsang
3. Kaedah Tatasusunan JavaScript Moden
   • Contoh 5: untukSetiap kaedah
   • Contoh 6: kaedah peta
   • Contoh 7: kaedah penapis
   • Contoh 8: kaedah kurangkan
4. Teknik Traversal Pertengahan
   • Contoh 9: Teknik dua mata
   • Contoh 10: Tetingkap gelongsor
   • Contoh 11: Algoritma Kadane
   • Contoh 12: Algoritma Bendera Kebangsaan Belanda
5. Teknik Traversal Lanjutan
   • Contoh 13: Rekursif lintasan
   • Contoh 14: Carian binari pada tatasusunan yang diisih
   • Contoh 15: Gabungkan dua tatasusunan yang diisih
   • Contoh 16: Algoritma Pilih Pantas
6. Perjalanan Khusus
   • Contoh 17: Melintasi tatasusunan 2D
   • Contoh 18: Spiral Matrix Traversal
   • Contoh 19: Traversal Diagonal
   • Contoh 20: Zigzag Traversal
7. Pertimbangan Prestasi
8. Masalah Amalan LeetCode
9. Kesimpulan

1. Pengenalan kepada Array Traversal

Traversal tatasusunan ialah proses melawati setiap elemen dalam tatasusunan untuk melaksanakan beberapa operasi. Ia merupakan kemahiran penting dalam pengaturcaraan, membentuk asas bagi banyak algoritma dan manipulasi data. Dalam JavaScript, tatasusunan ialah struktur data serba boleh yang menawarkan pelbagai cara untuk melintasi dan memanipulasi data.

2. Traversal Tatasusunan Asas

Mari kita mulakan dengan kaedah asas traversal tatasusunan.

Contoh 1: Menggunakan gelung for

Gelung klasik ialah salah satu cara paling biasa untuk merentasi tatasusunan.

function sumArray(arr) {
    let sum = 0;
    for (let i = 0; i 



<p><strong>Kerumitan Masa</strong>: O(n), dengan n ialah panjang tatasusunan.</p>

<p></p>

<h3>
  
  
  Contoh 2: Menggunakan gelung sementara
</h3>

<p>Gelung sementara juga boleh digunakan untuk traversal tatasusunan, terutamanya apabila keadaan penamatan lebih kompleks.<br>
</p>

<pre class="brush:php;toolbar:false">function findFirstNegative(arr) {
    let i = 0;
    while (i = 0) {
        i++;
    }
    return i 



<p><strong>Kerumitan Masa</strong>: O(n) dalam kes paling teruk, tetapi boleh kurang jika nombor negatif ditemui lebih awal.</p>

<p></p>

<h3>
  
  
  Contoh 3: Menggunakan gelung do-while
</h3>

<p>Gelung do-while adalah kurang biasa untuk traversal tatasusunan tetapi boleh berguna dalam senario tertentu.<br>
</p>

<pre class="brush:php;toolbar:false">function printReverseUntilZero(arr) {
    let i = arr.length - 1;
    do {
        console.log(arr[i]);
        i--;
    } while (i >= 0 && arr[i] !== 0);
}

const numbers = [1, 3, 0, 5, 7];
printReverseUntilZero(numbers); // Output: 7, 5

Kerumitan Masa: O(n) dalam kes yang paling teruk, tetapi boleh kurang jika sifar ditemui lebih awal.

Contoh 4: Reverse traversal

Melintasi tatasusunan dalam susunan terbalik ialah operasi biasa dalam banyak algoritma.

function reverseTraversal(arr) {
    const result = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        result.push(arr[i]);
    }
    return result;
}

const numbers = [1, 2, 3, 4, 5];
console.log(reverseTraversal(numbers)); // Output: [5, 4, 3, 2, 1]

Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan.

3. Kaedah Tatasusunan JavaScript Moden

ES6 dan versi JavaScript yang lebih baru memperkenalkan kaedah tatasusunan berkuasa yang memudahkan traversal dan manipulasi.

Contoh 5: untukSetiap kaedah

Kaedah forEach menyediakan cara yang bersih untuk mengulang elemen tatasusunan.

function logEvenNumbers(arr) {
    arr.forEach(num => {
        if (num % 2 === 0) {
            console.log(num);
        }
    });
}

const numbers = [1, 2, 3, 4, 5, 6];
logEvenNumbers(numbers); // Output: 2, 4, 6

Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan.

Contoh 6: kaedah peta

Kaedah peta mencipta tatasusunan baharu dengan hasil panggilan fungsi yang disediakan pada setiap elemen.

function doubleNumbers(arr) {
    return arr.map(num => num * 2);
}

const numbers = [1, 2, 3, 4, 5];
console.log(doubleNumbers(numbers)); // Output: [2, 4, 6, 8, 10]

Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan.

Contoh 7: kaedah penapis

Kaedah penapis mencipta tatasusunan baharu dengan semua elemen yang melepasi syarat tertentu.

function filterPrimes(arr) {
    function isPrime(num) {
        if (num 



<p><strong>Kerumitan Masa</strong>: O(n * sqrt(m)), dengan n ialah panjang tatasusunan dan m ialah nombor terbesar dalam tatasusunan.</p>

<p></p>

<h3>
  
  
  Contoh 8: kaedah mengurangkan
</h3>

<p>Kaedah pengurangan menggunakan fungsi pengurang pada setiap elemen tatasusunan, menghasilkan nilai output tunggal.<br>
</p>

<pre class="brush:php;toolbar:false">function findMax(arr) {
    return arr.reduce((max, current) => Math.max(max, current), arr[0]);
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMax(numbers)); // Output: 9

Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan.

4. Teknik Traversal Pertengahan

Sekarang mari kita terokai beberapa teknik perantaraan untuk traversal tatasusunan.

Contoh 9: Teknik dua mata

Teknik dua mata sering digunakan untuk menyelesaikan masalah berkaitan tatasusunan dengan cekap.

function isPalindrome(arr) {
    let left = 0;
    let right = arr.length - 1;
    while (left 



<p><strong>Time Complexity</strong>: O(n/2) which simplifies to O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 10: Sliding window
</h3>

<p>The sliding window technique is useful for solving problems involving subarrays or subsequences.<br>
</p>

<pre class="brush:php;toolbar:false">function maxSubarraySum(arr, k) {
    if (k > arr.length) return null;

    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 11: Kadane's Algorithm
</h3>

<p>Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.<br>
</p>

<pre class="brush:php;toolbar:false">function maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 12: Dutch National Flag Algorithm
</h3>

<p>This algorithm is used to sort an array containing three distinct elements.<br>
</p>

<pre class="brush:php;toolbar:false">function dutchFlagSort(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h2>
  
  
  5. Advanced Traversal Techniques
</h2>

<p>Let's explore some more advanced techniques for array traversal.</p>

<p></p>

<h3>
  
  
  Example 13: Recursive traversal
</h3>

<p>Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.<br>
</p>

<pre class="brush:php;toolbar:false">function sumNestedArray(arr) {
    let sum = 0;
    for (let element of arr) {
        if (Array.isArray(element)) {
            sum += sumNestedArray(element);
        } else {
            sum += element;
        }
    }
    return sum;
}

const nestedNumbers = [1, [2, 3], [[4, 5], 6]];
console.log(sumNestedArray(nestedNumbers)); // Output: 21

Time Complexity: O(n), where n is the total number of elements including nested ones.

Example 14: Binary search on sorted array

Binary search is an efficient algorithm for searching a sorted array.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left 



<p><strong>Time Complexity</strong>: O(log n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 15: Merge two sorted arrays
</h3>

<p>This technique is often used in merge sort and other algorithms.<br>
</p>

<pre class="brush:php;toolbar:false">function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i 



<p><strong>Time Complexity</strong>: O(n + m), where n and m are the lengths of the input arrays.</p>

<p></p>

<h3>
  
  
  Example 16: Quick Select Algorithm
</h3>

<p>Quick Select is used to find the kth smallest element in an unsorted array.<br>
</p>

<pre class="brush:php;toolbar:false">function quickSelect(arr, k) {
    if (k  arr.length) {
        return null;
    }

    function partition(low, high) {
        const pivot = arr[high];
        let i = low - 1;

        for (let j = low; j  k - 1) {
            return select(low, pivotIndex - 1, k);
        } else {
            return select(pivotIndex + 1, high, k);
        }
    }

    return select(0, arr.length - 1, k);
}

const numbers = [3, 2, 1, 5, 6, 4];
console.log(quickSelect(numbers, 2)); // Output: 2 (2nd smallest element)

Time Complexity: Average case O(n), worst case O(n^2), where n is the length of the array.

6. Specialized Traversals

Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.

Example 17: Traversing a 2D array

Traversing 2D arrays (matrices) is a common operation in many algorithms.

function traverse2DArray(matrix) {
    const result = [];
    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h3>
  
  
  Example 18: Spiral Matrix Traversal
</h3>

<p>Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.<br>
</p>

<pre class="brush:php;toolbar:false">function spiralTraversal(matrix) {
    const result = [];
    if (matrix.length === 0) return result;

    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;

    while (top = left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left = top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

const matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
];
console.log(spiralTraversal(matrix));
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 19: Diagonal Traversal

Diagonal traversal of a matrix is another interesting pattern.

function diagonalTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];

    for (let d = 0; d = 0 && j 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h3>
  
  
  Example 20: Zigzag Traversal
</h3>

<p>Zigzag traversal is a pattern where we traverse the array in a zigzag manner.<br>
</p>

<pre class="brush:php;toolbar:false">function zigzagTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];
    let row = 0, col = 0;
    let goingDown = true;

    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h2>
  
  
  7. Performance Considerations
</h2>

<p>When working with array traversals, it's important to consider performance implications:</p>

<ol>
<li><p><strong>Time Complexity</strong>: Most basic traversals have O(n) time complexity, where n is the number of elements. However, nested loops or recursive calls can increase this to O(n^2) or higher.</p></li>
<li><p><strong>Space Complexity</strong>: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.</p></li>
<li><p><strong>Iterator Methods vs. For Loops</strong>: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.</p></li>
<li><p><strong>Early Termination</strong>: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.</p></li>
<li><p><strong>Large Arrays</strong>: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.</p></li>
<li><p><strong>Caching Array Length</strong>: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.</p></li>
<li><p><strong>Avoiding Array Resizing</strong>: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.</p></li>
</ol>

<p></p><h2>
  
  
  8. Masalah Amalan LeetCode
</h2>

<p>Untuk mengukuhkan lagi pemahaman anda tentang teknik traversal tatasusunan, berikut ialah 15 masalah LeetCode yang boleh anda amalkan:</p>

<ol>
<li>Dua Jumlah</li>
<li>Masa Terbaik untuk Membeli dan Menjual Stok</li>
<li>Mengandungi Pendua</li>
<li>Produk Susunan Kecuali Diri</li>
<li>Subarray Maksimum</li>
<li>Gerakan Sifar</li>
<li>3Jumlah</li>
<li>Bekas dengan Kebanyakan Air</li>
<li>Susun Putar</li>
<li>Cari Minimum dalam Tatasusunan Isih Diputar</li>
<li>Cari dalam Tatasusunan Isih Diputar</li>
<li>Gabung Selang</li>
<li>Matriks Lingkaran</li>
<li>Tetapkan Sifar Matriks</li>
<li>Jujukan Berturut-turut Terpanjang</li>
</ol>

<p>Masalah ini merangkumi pelbagai teknik traversal tatasusunan dan akan membantu anda menggunakan konsep yang telah kami bincangkan dalam catatan blog ini.</p>

<p></p>

<h2>
  
  
  9. Kesimpulan
</h2>

<p>Traversal tatasusunan ialah kemahiran asas dalam pengaturcaraan yang menjadi asas kepada banyak algoritma dan manipulasi data. Daripada asas untuk gelung kepada teknik lanjutan seperti tingkap gelongsor dan traversal matriks khusus, menguasai kaedah ini akan meningkatkan keupayaan anda untuk menyelesaikan masalah kompleks dengan cekap dengan ketara.</p>

<p>Seperti yang anda lihat melalui 20 contoh ini, JavaScript menawarkan set alat yang kaya untuk traversal tatasusunan, masing-masing dengan kekuatan dan kes penggunaannya sendiri. Dengan memahami masa dan cara menggunakan setiap teknik, anda akan dilengkapkan dengan baik untuk menangani pelbagai cabaran pengaturcaraan.</p>

<p>Ingat, kunci untuk menjadi mahir adalah amalan. Cuba laksanakan kaedah traversal ini dalam projek anda sendiri, dan jangan teragak-agak untuk meneroka teknik yang lebih maju sambil anda semakin selesa dengan asasnya. Masalah LeetCode yang disediakan akan memberi anda peluang yang luas untuk menggunakan konsep ini dalam pelbagai senario.</p>

<p>Sambil anda terus mengembangkan kemahiran anda, sentiasa ingat implikasi prestasi kaedah traversal pilihan anda. Kadangkala, gelung mudah mungkin merupakan penyelesaian yang paling cekap, manakala dalam kes lain, teknik yang lebih khusus seperti tetingkap gelongsor atau kaedah dua penuding boleh menjadi optimum.</p>

<p>Selamat pengekodan, dan semoga tatasusunan anda sentiasa dilalui dengan cekap!</p>


          

            
        

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