JavaScript 算法和数据结构大师课程

2025年4月19日 | 阅读 15 分钟

引言

数据结构和算法构成了软件工程和编程的基础。它们是高效解决复杂问题的基本工具，对于构建健壮且可扩展的应用程序至关重要。

在本大师班中，我们将深入探讨 JavaScript 算法和数据结构的世界。无论您是希望巩固基本知识的初学者，还是希望提高解决问题能力的经验丰富的开发人员，本大师班都旨在满足广泛受众的需求。

1. 变量、数据类型和运算符

在 JavaScript 中，变量用于存储和操作数据。我们应该从探索变量、数据类型和运算符的基础知识开始。

示例代码

// Variables and Data Types
let age = 25;  
let name = " Johnny ";  

// Arithmetic Operators
let sum = age + 5;  
let product = age * 2;  

// String Concatenation
let greeting = " Hello, " + name + " ! ";  

// Variables and Data Types
let age = 25;  
let name = " Johnny ";  

// Arithmetic Operators
let sum = age + 5;  
let product = age * 2;  

// String Concatenation
let greeting = " Hello, " + name + " ! ";  

2. 控制流和条件语句

控制流结构允许您指导代码的执行顺序。条件语句，例如 if、else if 和 else，对于在项目中做出决策至关重要。

示例代码

// If-Else Statement
let hour = 14;

if ( hour < 12 ) {
    console.log(" Good morning! ");
} else if ( hour < 18 ) {
    console.log(" Good afternoon! ");
} else {
    console.log(" Good evening! ");
}

条件语句是根据特定条件执行不同代码块的有用工具。它们在算法问题解决中起着重要作用。

JavaScript 中的循环和迭代

循环提供了一种重复执行代码块的方法。JavaScript 支持多种类型的循环，包括 for、while 和 do-while。这些对于遍历数组或对象或多次执行一系列指令至关重要。

示例

// For Loop
for ( let i = 0; i < 5; i++ ) {
    console.log(" Iteration : " + i );
}

// While Loop
let count = 0;
while ( count < 3 ) {
    console.log(" Count : " + count );
    count++;
}

JavaScript 中的函数和作用域

函数是可重用的代码块，可以接受输入、执行任务并返回结果。它们在组织代码和促进重用性方面发挥着关键作用。作用域是指变量在代码不同部分的可访问性。

示例

// Function Declaration
function greet(name) {
    console.log(" Hello, " + name + "!");
}

// Example 2.4.2: Function Invocation
greet(" Priya ");

// Example 2.4.3: Scope
let globalVar = " I am global ";

function exampleScope() {
    let localVar = " I am local ";
    console.log( globalVar );  // Accessing global variable
    console.log( localVar );   // Accessing local variable
}

exampleScope();

3. 时间复杂度和空间复杂度

时间复杂度是指算法完成所需的时间，它是输入数据大小的函数。另一方面，空间复杂度衡量算法在执行期间使用的内存量。

最佳、最差和平均情况

算法的行为可能会因输入数据的属性而异。最佳情况表示最优输入，而最差情况表示最不利的输入。平均情况考虑了各种输入源的平均执行情况。

示例代码

// Time Complexity - O(n)
function linearTimeComplexity( arr ) {
    for ( let i = 0; i < arr.length; i++ ) {
        console.log( arr[ i ]);
    }
}

// Space Complexity - O(1)
function constantSpaceComplexity( arr ) {
    let sum = 0;
    for ( let i = 0; i < arr.length; i++ ) {
        sum += arr[ i ];
    }
    return sum;
}

4. 数组和字符串

数组和字符串是 JavaScript 中核心的数据结构。数组允许您存储和操作元素的集合，而字符串是字符序列。

数组

数组是有序的、索引的元素集合。在 JavaScript 中，数组可以包含不同的数据类型，并且对于存储和操作元素非常灵活。理解它们的属性和方法对于有效的解决问题至关重要。

示例

let numbers = [ 1, 2, 3, 4, 5 ];
let fruits = [ " apple ", " banana ", " orange " ];

数组操作和运算

JavaScript 中的数组带有各种内置方法用于操作和运算，例如添加或删除元素、搜索元素以及修改数组。

示例

// Adding Elements to an Array
fruits.push( " grape " );  // Adds " grape " to the end of the ' fruits ' array

// Removing Elements from an Array
numbers.pop();  // Removes the last element from the ' numbers ' array

// Searching for an Element in an Array
let index = fruits.indexOf( " banana " );  // Returns the index of " banana " in the ' fruits ' array

问题：查找缺失的数字

给定一个包含从 1 到 n 的整数的数组，其中一个数字缺失，找出缺失的数字。

// Finding the Missing Number
function findMissingNumber( arr  ) {
    const n = arr.length + 1;
    const totalSum = ( n * (n + 1) ) / 2;
    const actualSum = arr.reduce(( sum, num ) => sum + num, 0 );
    return totalSum - actualSum;
}

let numbersWithMissing = [ 1, 2, 4, 5, 6 ];
let missingNumber = findMissingNumber( numbersWithMissing );
console.log( " Missing Number: ", missingNumber );

字符串

字符串是字符序列，在 JavaScript 中被视为不可变。它们提供了许多操作方法，并经常用于文本处理。

示例

字符串操作方法

可以使用各种方法在 JavaScript 中操作字符串，例如通过连接、切片和搜索。

示例

// Changing Case
let upperCaseMessage = message.toUpperCase();  // Converts ' message ' to uppercase

// Replacing Substrings
let replacedMessage = message.replace( " World ", " Universe ");  // Replaces " World " with " Universe "

// Splitting a String
let words = message.split(", ");  // Splits ' message ' into an array using ", " as the separator

5. 链表

链表是一种线性数据结构，其中元素存储在节点中，每个节点指向序列中的下一个节点。与数组不同，链表提供动态内存分配以及高效的插入和删除。

链表是基本的数据结构，由一系列元素组成，每个元素都通过指针或引用连接。与数组不同，链表没有固定大小，允许动态内存分配。它们有各种结构，每种结构都有其优点和用例。

单向链表

在单向链表中，每个节点包含数据和指向序列中下一个节点的引用。最后一个节点指向 null，表示列表的结束。单向链表在插入和删除操作方面效率很高，但它们在反向访问元素方面受到限制。

示例

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    // Methods for insertion, deletion, traversal, etc.
}

双向链表

双向链表扩展了单向链表，每个节点都包含指向下一个节点和上一个节点的引用。这种双向链接允许在正向和反向中进行高效的遍历。然而，这需要额外的内存来存储前向指针。

示例

class Node {
    constructor( data ) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // Methods for insertion, deletion, traversal, etc.
}

6. 栈和队列

Stack

栈是一种后进先出 (LIFO) 数据结构，其中元素从同一个末端（称为“栈顶”）添加和删除。这使其在管理函数调用、跟踪执行历史和处理撤销操作方面特别有用。

示例

class Stack {
    constructor() {
        this.items = [ ];
    }

    // Methods for push, pop, peek, isEmpty, size, etc.
}

Queue

队列是一种先进先出 (FIFO) 数据结构，其中元素在队尾添加（入队）并在队首删除（出队）。队列通常用于任务调度、图中的广度优先搜索和打印作业管理等情况。

示例

class Queue {
    constructor() {
        this.items = [ ];
    }

    // Methods for enqueue, dequeue, front, isEmpty, size, etc.
}

7. 递归

递归是一种编程概念，其中函数调用自身来解决问题的一个较小实例。它涉及将一个复杂的问题分解为更简单、相同的子问题。在 JavaScript 中，递归函数有一个基本情况来防止无限递归。

示例

// Factorial Calculation using Recursion
function factorial( n ) {
    if (n === 0 || n === 1) {
        return 1;  // Base case
    } else {
        return n * factorial( n - 1 );  // Recursive case
    }
}

递归算法

递归常用于各种算法。例如，

二分查找：将排序数组划分为相等的部分。
斐波那契数列：使用递归调用生成斐波那契数。
树遍历：递归地遍历树结构。

示例

// Recursive Binary Search
function binarySearch( arr, target, start, end ) {
    if (start > end) {
        return -1;  // Base case: element not found
    }

    let mid = Math.floor(( start + end ) / 2);

    if ( arr[ mid ] === target) {
        return mid;  // Base case: element found
    } else if ( arr[ mid ] > target) {
        return binarySearch( arr, target, start, mid ? 1 );  // Recursive case: search left half
    } else {
        return binarySearch( arr, target, mid + 1, end );  // Recursive case: search right half
    }
}

8. 排序算法

排序是软件工程中的一项基本操作，存在各种排序算法，每种算法都有其优点和缺点。排序算法对于高效地组织和组织数据至关重要。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序。

冒泡排序

冒泡排序反复遍历列表，比较相邻的元素，如果它们的顺序错误则进行交换。列表的遍历会重复进行，直到不再需要交换。

示例代码

// Bubble Sort Implementation
function bubbleSort( arr ) {
    const n = arr.length;
    for ( let i = 0; i < n - 1; i++ ) {
        for ( let j = 0; j < n - i - 1; j++ ) {
            if ( arr[ j ] > arr[ j + 1 ]) {
                // Swap elements if they are in the wrong order
                [ arr[ j ], arr[ j + 1 ]] = [ arr[ j + 1 ], arr[ j ]];
            }
        }
    }
    return arr;
}

选择排序

选择排序将输入列表分为已排序和未排序区域。它反复从未排序区域中选择最小（或最大）的元素，并将其与未排序区域的第一个元素进行交换。

示例代码

// Selection Sort Implementation
function selectionSort( arr ) {
    const n = arr.length;
    for ( let i = 0; i < n - 1; i++ ) {
        let minIndex = i;
        for ( let j = i + 1; j < n; j++ ) {
            if ( arr[ j ] < arr[ minIndex ]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element
        [ arr[ i ], arr[ minIndex ]] = [ arr[ minIndex ], arr[i]];
    }
    return arr;
}

插入排序

插入排序一次构建一个已排序的数组。对于大型列表，它比快速排序、堆排序或归并排序等更高级的算法效率要低得多。

示例代码

// Insertion Sort Implementation
function insertionSort( arr ) {
    const n = arr.length;
    for ( let i = 1; i < n; i++ ) {
        let key = arr[i];
        let j = i - 1;

        // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while ( j >= 0 && arr[ j ] > key ) {
            arr[ j + 1 ] = arr[j];
            j--;
        }
        arr[ j + 1 ] = key;
    }
    return arr;
}

合并排序

归并排序是一种分治算法，它将未排序列表分解为 n 个子列表，每个子列表包含一个元素，然后反复合并子列表以生成新的已排序子列表。

示例代码

// Merge Sort Implementation
function mergeSort( arr ) {
    if ( arr.length <= 1 ) {
        return arr;
    }

    const mid = Math.floor( arr.length / 2 );
    const left = arr.slice( 0, mid );
    const right = arr.slice( mid );

    return merge(mergeSort( left ), mergeSort( right ));
}

function merge( left, right ) {
    let result = [ ];
    let i = 0;
    let j = 0;

    while ( i < left.length && j < right.length ) {
        if ( left[i] < right[j] ) {
            result.push( left[i] );
            i++;
        } else {
            result.push( right[j] );
            j++;
        }
    }

    return result.concat( left.slice(i), right.slice(j) );
}

快速排序

快速排序是另一种分治算法，它选择一个“枢轴”元素，并将其他元素根据它们是否小于或大于枢轴划分为两个子数组。

示例代码

// Quick Sort Implementation
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[ arr.length ? 1 ];
    const left = [];
    const right = [];

    for ( let i = 0; i < arr.length - 1; i++ ) {
        if ( arr[i] < pivot ) {
            left.push( arr[i] );
        } else {
            right.push( arr[i] );
        }
    }

    return [ . . . quickSort( left ), pivot, . . . quickSort( right )];
}

9. 搜索算法

线性搜索

线性搜索是一种简单的搜索算法，它按顺序检查列表中的每个元素，直到找到匹配项或搜索完整个列表。它很简单，但对于大型数据集可能效率不高。

示例代码

// Linear Search Implementation in JavaScript
function linearSearch( arr, target ) {
    for ( let i = 0; i < arr.length; i++ ) {
        if ( arr[ i ] === target ) {
            return i;  // Return the index if the target is found
        }
    }
    return -1;  // Return -1 if target is not found
}

二分搜索

二分查找是一种高效的排序数组搜索算法。它通过反复将搜索范围分成相等的两部分来工作。

示例代码

// Binary Search Implementation in JavaScript
function binarySearch( arr, target ) {
    let low = 0;
    let high = arr.length - 1;

    while ( low <= high ) {
        let mid = Math.floor(( low + high ) / 2);

        if ( arr[ mid ] === target) {
            return mid;  // Return the index if the target is found
        } else if ( arr[ mid ] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;  // Return -1 if target is not found
}

10. 树和图

树和图是分层数据结构，它们组织和表示元素之间的关系。

树

树是一种分层数据结构，有一个根元素和一组子元素。每个子元素都有一个父节点（根节点除外），没有子节点的元素称为叶子节点。

示例代码

// Tree Node Implementation
class TreeNode {
    constructor( value ) {
        this.value = value;
        this.children = [ ];
    }

    // Methods for adding, removing, traversing nodes, etc.
}

二叉树和二叉搜索树

二叉树是一种树形数据结构，其中每个节点有两个子节点，称为左子节点和右子节点。二叉搜索树 (BST) 是一种二叉树，其中节点的左子树包含值小于节点值的节点，右子树包含值大于节点值的节点。

示例代码

// Binary Search Tree Implementation
class TreeNode {
    constructor( value ) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    // Methods for insertion, deletion, searching, etc.
}

图

图是节点集合和连接节点对的边。图可以是定向的或无向的，并且可以具有加权边。

示例代码

// Graph Representation using Adjacency List
class Graph {
    constructor() {
        this.vertices = { };
    }

    // Methods for adding vertices, edges, traversing, etc.
}

图遍历

图遍历算法有助于探索和检查图内的关系。两种常见的算法是深度优先搜索 (DFS) 和广度优先搜索 (BFS)。

示例代码

// Depth-First Search ( DFS ) Implementation
function dfs( graph, startVertex, visited = { } ) {
    if ( !graph.vertices[ startVertex ]) {
        return;
    }

    console.log( startVertex );
    visited[ startVertex ] = true;

    for ( const neighbor of graph.vertices [ startVertex ]) {
        if ( !visited [ neighbor ]) {
            dfs( graph, neighbor, visited );
        }
    }
}

// Breadth-First Search ( BFS ) Implementation
function bfs( graph, startVertex ) {
    const queue = [ ];
    const visited = { };

    if ( graph.vertices[ startVertex ]) {
        queue.push( startVertex );
        visited[ startVertex ] = true;

        while ( queue.length > 0 ) {
            const currentVertex = queue.shift( );
            console.log( currentVertex );

            for ( const neighbor of graph.vertices [ currentVertex ]) {
                if ( !visited [ neighbor ]) {
                    queue.push( neighbor );
                    visited[ neighbor ] = true;
                }
            }
        }
    }
}

11. 位操作

位操作涉及在数据的二进制表示中操作单个位。它是一种强大的技术，通常用于优化计算和高效处理特定问题。位操作通常用于优化存储、检查特定位的存在以及在位级别执行数字运算等情况。

示例代码

// Bitwise AND Operation
const result = 5 & 3;  // Binary: 101 & 011 = 001 (Decimal: 1)

// Bitwise OR Operation
const result = 5 | 3;  // Binary: 101 | 011 = 111 (Decimal: 7)

// Bitwise XOR Operation
const result = 5 ^ 3;  // Binary: 101 ^ 011 = 110 (Decimal: 6)

// Left Shift Operation
const result = 5 << 1;  // Binary: 101 << 1 = 1010 (Decimal: 10)

// Right Shift Operation
const result = 5 >> 1;  // Binary: 101 >> 1 = 10 (Decimal: 2)

12. 堆和优先队列

堆

堆是一种特殊的数据结构，它满足堆属性。在最大堆中，对于任何随机节点 C 和其父节点 P，P 的值大于或等于 C 的值。在最小堆中，P 的值小于或等于 C 的值。

示例代码

// Min Heap Implementation
class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Methods for insertion, deletion, heapify, etc.
}

优先队列

优先队列是一种抽象数据类型，其工作方式类似于标准队列。但是，每个元素都被分配了一个优先级级别。具有较高优先级的元素先于具有较低优先级的元素被处理。

示例代码

// Priority Queue Implementation
class PriorityQueue {
    constructor() {
        this.heap = new MinHeap();
    }

    // Methods for enqueue, dequeue, peek, etc.
}

13. 动态规划

动态规划是一种强大的优化技术，通过将问题分解为更简单的子问题来解决问题，仅解决每个子问题一次，并将答案存储起来以备将来参考。它对于具有重叠子问题和最优子结构的常见问题特别有用。

记忆化

记忆化是一种缓存昂贵函数调用结果的技术，当遇到相同的输入时。它通常使用哈希表等数据结构来实现。

示例代码

// Example 11.2.1: Memoization in Fibonacci Calculation
function fibMemo(n, memo = {}) {
    if (n <= 1) {
        return n;
    }

    if (!memo[n]) {
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    }

    return memo[n];
}

制表

制表是一种自底向上的方法，其中通过解决所有子问题并将它们的结果存储在表中来解决问题。它通常涉及在循环中填充表，从最小的子问题开始。

示例代码

// Tabulation in Fibonacci Calculation
function fibTab(n) {
    const table = new Array(n + 1).fill(0);
    table[1] = 1;

    for (let i = 2; i <= n; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }

    return table[n];
}

结论

在本套关于算法和数据结构的完整大师班中，我们从基本概念到高级应用进行了一次旅程，探索了实现高效问题解决和算法推理的基本构建块。我们深入研究了数据结构的复杂性，理解了它们在组织和管理数据方面的作用。

从数组和字符串到链表、栈和队列，我们探讨了它们的应用程序和复杂性。树和图使我们能够表示分层关系和复杂连接，而堆和优先队列则促进了高效的优先级排序。

下一主题如何计算 JavaScript 中的日期差

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

JavaScript 基础

JS 变量和数据类型

JS 控制语句

JavaScript 函数

JavaScript 对象

JS 高级函数

JS Promises & Async/Await

JavaScript DOM

JavaScript JSON 对象

JavaScript 验证

JavaScript Cookies

异常处理

JavaScript 集合

JavaScript 事件

JavaScript OOPs

JavaScript BOM

面试题

选择题

差异

JavaScript Map 方法

JavaScript Handler

JavaScript Number 方法

JavaScript Reflect

JavaScript Symbol

Symbol 属性

JavaScript Math 方法

JavaScript Date 方法

JavaScript DataView

JavaScript Object 方法

JavaScript Set 方法

JavaScript 字符串方法

JavaScript TypedArray 方法

JavaScript WeakMap 方法

JavaScript WeakSet 方法

JavaScript 数组方法

JavaScript RegExp 对象

JavaScript 附加内容

JavaScript 杂项

JavaScript 进阶

问题

Lodash

JavaScript 算法和数据结构大师课程

引言

1. 变量、数据类型和运算符

2. 控制流和条件语句

JavaScript 中的循环和迭代

JavaScript 中的函数和作用域

3. 时间复杂度和空间复杂度

最佳、最差和平均情况

4. 数组和字符串

数组

数组操作和运算

问题：查找缺失的数字

字符串

字符串操作方法

5. 链表

单向链表

双向链表

6. 栈和队列

Stack