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 < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

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

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

Contoh 2: Menggunakan gelung sementara

Gelung sementara juga boleh digunakan untuk traversal tatasusunan, terutamanya apabila keadaan penamatan lebih kompleks.

function findFirstNegative(arr) {
    let i = 0;
    while (i < arr.length && arr[i] >= 0) {
        i++;
    }
    return i < arr.length ? arr[i] : "No negative number found";
}

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

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

Contoh 3: Menggunakan gelung do-while

Gelung do-while adalah kurang biasa untuk traversal tatasusunan tetapi boleh berguna dalam senario tertentu.

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 <= 1) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    return arr.filter(isPrime);
}

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

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

Contoh 8: kaedah mengurangkan

Kaedah pengurangan menggunakan fungsi pengurang pada setiap elemen tatasusunan, menghasilkan nilai output tunggal.

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 < right) {
        if (arr[left] !== arr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

console.log(isPalindrome([1, 2, 3, 2, 1])); // Output: true
console.log(isPalindrome([1, 2, 3, 4, 5])); // Output: false

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

Example 10: Sliding window

The sliding window technique is useful for solving problems involving subarrays or subsequences.

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 < 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;
}

const numbers = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSubarraySum(numbers, 4)); // Output: 39

Time Complexity: O(n), where n is the length of the array.

Example 11: Kadane's Algorithm

Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.

function maxSubarraySum(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;
}

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

Time Complexity: O(n), where n is the length of the array.

Example 12: Dutch National Flag Algorithm

This algorithm is used to sort an array containing three distinct elements.

function dutchFlagSort(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--;
        }
    }

    return arr;
}

const numbers = [2, 0, 1, 2, 1, 0];
console.log(dutchFlagSort(numbers)); // Output: [0, 0, 1, 1, 2, 2]

Time Complexity: O(n), where n is the length of the array.

5. Advanced Traversal Techniques

Let's explore some more advanced techniques for array traversal.

Example 13: Recursive traversal

Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.

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 <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedNumbers, 7)); // Output: 3
console.log(binarySearch(sortedNumbers, 6)); // Output: -1

Time Complexity: O(log n), where n is the length of the array.

Example 15: Merge two sorted arrays

This technique is often used in merge sort and other algorithms.

function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            mergedArray.push(arr1[i]);
            i++;
        } else {
            mergedArray.push(arr2[j]);
            j++;
        }
    }

    while (i < arr1.length) {
        mergedArray.push(arr1[i]);
        i++;
    }

    while (j < arr2.length) {
        mergedArray.push(arr2[j]);
        j++;
    }

    return mergedArray;
}

const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity: O(n + m), where n and m are the lengths of the input arrays.

Example 16: Quick Select Algorithm

Quick Select is used to find the kth smallest element in an unsorted array.

function quickSelect(arr, k) {
    if (k < 1 || k > arr.length) {
        return null;
    }

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

        for (let j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }

        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }

    function select(low, high, k) {
        const pivotIndex = partition(low, high);

        if (pivotIndex === k - 1) {
            return arr[pivotIndex];
        } else if (pivotIndex > 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 < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

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

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

Example 18: Spiral Matrix Traversal

Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.

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 <= bottom && left <= right) {
        // Traverse right
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;

        // Traverse down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;

        if (top <= bottom) {
            // Traverse left
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse up
            for (let i = bottom; i >= 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 < m + n - 1; d++) {
        const temp = [];
        for (let i = 0; i < m; i++) {
            const j = d - i;
            if (j >= 0 && j < n) {
                temp.push(matrix[i][j]);
            }
        }
        if (d % 2 === 0) {
            result.push(...temp.reverse());
        } else {
            result.push(...temp);
        }
    }

    return result;
}

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

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

Example 20: Zigzag Traversal

Zigzag traversal is a pattern where we traverse the array in a zigzag manner.

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 < m * n; i++) {
        result.push(matrix[row][col]);

        if (goingDown) {
            if (row === m - 1 || col === 0) {
                goingDown = false;
                if (row === m - 1) {
                    col++;
                } else {
                    row++;
                }
            } else {
                row++;
                col--;
            }
        } else {
            if (col === n - 1 || row === 0) {
                goingDown = true;
                if (col === n - 1) {
                    row++;
                } else {
                    col++;
                }
            } else {
                row--;
                col++;
            }
        }
    }

    return result;
}

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

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

7. Performance Considerations

When working with array traversals, it's important to consider performance implications:

1. Time Complexity: 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.

2. Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.

3. Iterator Methods vs. For Loops: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.

4. Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.

5. Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.

6. Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.

7. Avoiding Array Resizing: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.

8. Masalah Amalan LeetCode

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

1. Dua Jumlah
2. Masa Terbaik untuk Membeli dan Menjual Stok
3. Mengandungi Pendua
4. Produk Susunan Kecuali Diri
5. Subarray Maksimum
6. Gerakan Sifar
7. 3Jumlah
8. Bekas dengan Kebanyakan Air
9. Susun Putar
10. Cari Minimum dalam Tatasusunan Isih Diputar
11. Cari dalam Tatasusunan Isih Diputar
12. Gabung Selang
13. Matriks Lingkaran
14. Tetapkan Sifar Matriks
15. Jujukan Berturut-turut Terpanjang

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

9. Kesimpulan

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.

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.

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.

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.

Selamat pengekodan, dan semoga tatasusunan anda sentiasa dilalui dengan cekap!

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!